Submission #1871449

---

Source Code Expand

import random
import time
import sys
import math
import numpy as np

MAX_V=500
MAX_E=20000
MAX_V_EMB=3600
MAX_N=60

TIME_LIMIT=25

startTime=0
endTime=0
V=0
E=0
N=0
Vemb=0
Eemb=0
DD=[]

edgesMapG=[[False for i in range(MAX_V)] for j in range(MAX_V)]
isPairMapG=[[False for i in range(MAX_V)] for j in range(MAX_V)]
edgesMapGemb=[[False for i in range(MAX_V_EMB)] for j in range(MAX_V_EMB)]
vertexMapping=[-1]*MAX_V # V -> Vemb
vertexMapGemb=[-1]*MAX_V_EMB # Vemb -> V
dist=[[0 for i in range(MAX_V)] for j in range(MAX_V)] # distance from vi to vj in Vemb
groups=[[] for i in range(MAX_V)]

edgeList=[]

class Edge:
	""" from -> u; to -> v; cost -> c """
	u=-1
	v=-1
	def __init__(self):
		self.name=""

	def __init__(self, u, v):
		self.u=u
		self.v=v

	def getName(self):
		return self.name

	def setName(self, name):
		self.name=name


def read_graph():
	global V,E
	V,E=map(int,input().split())
	global edgesMapG
	for i in range(E):
		u,v,=map(int,input().split())
		u-=1
		v-=1
#		union_find_unite(u,v)
		edgesMapG[u][v] = True
		edgesMapG[v][u] = True

def calc_grouping():
	global V, vertexMapping, groups
	for i in range(V):
		groups[i] += [vertexMapping[i]]	# V -> Vemb cation! vertexMapping[i] is not only one value!

def calc_edgeList():
	global V, edgesMapG, edgeList
	for i in range(V):
		for j in range(V):
			if edgesMapG[i][j] == True:
				edgeList.append(Edge(i,j))

def calc_isPairMapG():
	global DD, Vemb, vertexMapGemb, isPairMapG, N

	for i in range(Vemb):
		v = vertexMapGemb[i]	# Vemb -> V
		for d in range(8):
			z = i + DD[d]
			if z < 0 or z >= Vemb:
				continue
			if ((i + 1) % N) == 0 and (d == 2 or d == 3 or d == 4):
				continue
			if (i % N) == 0 and (d == 0 or d == 6 or d == 7):
				continue
			u = vertexMapGemb[z] # Vemb -> V
			if edgesMapG[v][u] == True:
				isPairMapG[v][u] |= True
				isPairMapG[u][v] |= True
def calc_dist(u,v):
	global Vemb,groups,N

	res=Vemb
	for i in groups[u]:	# for Vemb
		for j in groups[v]:	# for Vemb
			row = abs(i // N - j // N)
			col = abs(i % N - j % N)
			curr = abs(row - col)
			res = min(res, curr)
	return res

def calc_distance():
	global V, vertexMapGemb, isPairMapG, dist

	for i in range(V):
		for j in range(V):
			if dist[i][j] == 1:
				isPairMapG[i][j] |= True
			else:
				isPairMapG[i][j] = False
	for i in range(V):
		for j in range(V):
			if i == j:
				dist[i][j] = 0
			elif isPairMapG[i][j] == True:
				dist[i][j] = 1
			else:
				dist[i][j] = calc_dist(i,j)
	for i in range(V):
		for i in range(V):
			if dist[i][j] == 1:
				isPairMapG[i][j] |= True
			else:
				isPairMapG[i][j] = False
			
def read_KingGraph():
	global Vemb, Eemb, N;
	Vemb,Eemb=map(int,input().split())
	N = int(Vemb**0.5 + 0.5)

	global edgesMapG, edgesMapGemb

	for i in range(Eemb):
		a,b=map(int,input().split())
		edgesMapGemb[a-1][b-1] = True;
		edgesMapGemb[b-1][a-1] = True;

	N=int(Vemb**0.5 + 0.5)
	global DD
	DD.append(- N - 1)
	DD.append(- N)
	DD.append(- N + 1)
	DD.append(1)
	DD.append(N + 1)
	DD.append(N)
	DD.append(N - 1)
	DD.append(-1)

def calc_mds():
	global V, E
	d=[[0 for i in range(V)] for j in range(V)]
	for i in range(V):
		for j in range(V):
			if i == j:
				continue
			elif edgesMapG[i][j] == True:
				d[i][j] = 1
			else:
				sz = int(math.ceil(math.sqrt(sum(edgesMapG[i]))))
				d[i][j] = sz

	D=np.array(d)
	N0=len(D)
	S=D*D
	one=np.eye(N0) - np.ones((N0,N0))/N0
	P= -1.0 / 2 * one * S * one
	w,v=np.linalg.eig(P)
	ind=np.argsort(w)
	x1=ind[-1]
	x2=ind[-2]
	s=P.std(axis=0)
	w1=s[x1]
	w2=s[x2]

	posX=[]
	posY=[]
	for i in range(N0):
		posX.append(w1*v[i,x1])
		posY.append(w2*v[i,x2])

	return posX,posY,ind

def TransKingGraph(posX,posY,ind):
	global V,Vemb
	global vertexMapping
	global vertexMapGemb

	posXmin=min(posX)
	posXmax=max(posX)
	posYmin=min(posY)
	posYmax=max(posY)

	diffX=posXmax-posXmin
	diffY=posYmax-posYmin

	N=int(Vemb**0.5+0.5)
	n=int(V**0.5+0.5)
	offset=(N-n)//2

	used=set()
	for i in range(V):
		px=int((posX[ind[i]] - posXmin) / diffX*(N-1))
		py=int((posY[ind[i]] - posYmin) / diffY*(N-1))
		z= py * N + px
		if z not in used:
			vertexMapping[ind[i]] = z	# V -> Vemb 
			vertexMapGemb[z] = ind[i]	# Vemb -> V
			used.add(z)
		else:
			find=False
			l=1
			while l <= 10:
				for k in range(8):
					nz = z + l * DD[k]
					if nz < 0 or nz >= N * N:
						continue
					if vertexMapGemb[nz] != -1:
						continue
					vertexMapping[ind[i]] = nz # V -> Vemb
					vertexMapGemb[nz] = ind[i] # Vemb -> V
					used.add(nz)
					find = True
					break
				if find:
					break
				l+=1
			if find == False:
				while True:
					r=random.randint(0,Vemb-1)
#					print("random:",r,file=sys.stderr)
					if vertexMapGemb[r] == -1 and r not in used:
						vertexMapping[ind[i]] = r # V -> Vemb
						vertexMapGemb[r] = ind[i] # Vemb -> V
						used.add(r)
						break
def disp_res():
	global V, groups
	for i in range(V):
		sz = len(groups[i])
		print(sz, " ", end="")
		for j in groups[i]:
			print(j + 1, " ", end="")
		print("")

def HillClimbing():
	global TIME_LIMIT
	global startTime
	global endTime
	global DD, dist, edgeList,N

	currentScore = np.sum(dist)
#	print("currentScore:", currentScore, file=sys.stderr)
	bestScore = currentScore
	es = len(edgeList)
	random.shuffle(edgeList)

	diffScore = 0
	iteration = 0
	currentTime = time.time()
	while currentTime - startTime < endTime:
		currentTime = time.time()
		e = iteration % es
		edges = edgeList[e]
		u = edges.u	# for V
		v = edges.v	# for V
		if isPairMapG[u][v] == True:
			iteration += 1
			continue
		else:
			cand = random.choice(groups[u])	# for Vemb
			find = False
			z = -1

#			if u == 32:
#				print("cand:", cand, file=sys.stderr)

			for d in range(8):
				z = cand + DD[d]
				if z < 0 or z >= Vemb:
					continue
				if ((cand + 1) % N) == 0 and (d == 2 or d == 3 or d == 4):
					continue
				if (cand % N) == 0 and (d == 0 or d == 6 or d == 7):
					continue
#				if u == 32:
#					print("newz:", z, file=sys.stderr)

				if vertexMapGemb[z] == -1:
					vertexMapGemb[z] = u
					groups[u] += [z]
					find = True
					break
#			if u == 32:
#				print("group[",u,"]:", groups[u], file=sys.stderr)
#				for i in groups[u]:
#					px = i % N
#					py = i // N
#					print("(",px,",",py,")", file=sys.stderr)
					
			if find == True:
				calc_distance()
				currentScore = np.sum(dist)
				if currentScore <= bestScore:
					bestScore = currentScore
				else:
					vertexMapGemb[z] = -1
					print("group[",u,"]:", groups[u], file=sys.stderr);
					groups[u].delete(z)
					calc_distance()
		iteration += 1

	print("iteration:", iteration, file=sys.stderr)


def main():
	global TIME_LIMIT
	global startTime
	global endTime
	startTime = time.time()
	endTime = TIME_LIMIT

	read_graph()
	read_KingGraph()
	posX, posY, ind = calc_mds()
	TransKingGraph(posX,posY,ind)
	calc_grouping()
	calc_edgeList()
	
	calc_isPairMapG()
	calc_distance()

	HillClimbing()
	disp_res()
if __name__ == '__main__':
	main()

Submission Info

Judge Result