本来今天说偷下懒,不写题了,结果晚上的时候yzc大佬和我说有一道题一直WA,叫我给他搞点数据过来。然后就开始搞数据,搞了一晚上,就是需要用生成这样的数据,还比较复杂。
题目链接
第一行 教室数量 管道数量 0<N<=10000,0<M<20000
第二行 教室数量个数字 0<=Vi<=1000
第三到3+M行 每行两个数字 要求生成的这n行属于同个集合
啊啊啊 第一次感受到用算法解决实际问题的快感。
import random
import numpy as np
def find(x):
while tempList[x] != x:
x = tempList[x]
return x
def merge(i, j):
fi = find(i)
fj = find(j)
if tempList[fi] != tempList[fj]:
tempList[fi] = fj
with open("D:/input.txt", "a") as f:
for i in range(10):
classroomNum = int(random.random()*100)
pipelineNum = classroomNum+50
maps = np.random.randint(0, classroomNum, (pipelineNum,2))
tempList = [i for i in range(classroomNum)]
for m in range(len(maps)):
if maps[m][0] != maps[m][1]:
merge(tempList[maps[m][0]], tempList[maps[m][1]])
#获取管道数
num = 0
for k,v in enumerate(tempList):
if(k != v):
num+=1
#输出教室数和管道数
f.write(str(classroomNum)+" "+str(num)+"\n")
#随机输出各个教室的人数
for i in range(classroomNum):
f.write(str(int(random.random()*1000))+" ")
f.write("\n")
#写入
for k,v in enumerate(tempList):
if(k != v):
f.write(str(k)+" "+str(v)+"\n")