超能饮料~~暂时告一段路吧

gistfile1.py

#!/usr/bin/python
# encoding:utf-8
"""
题目: http://www.wmsstech.com/puzzles_view_chemical.html

本解法是,取一个最小环,然后不断的往里面加点
当加点时,尝试该点的所有入度出度的组合
当尝试某个组合时,譬如 加入点k, 使用的组合是 x->k, k->y
那么找到x的出度,尝试将他转移到k,y,以及y的可达点,看能否获得一个更好的组合
然后找到y的入度,尝试转移到k,x以及x的来路上,看能否获得一个更好的组合

目前这个解法,碰到的问题是,某些点是从x出去,然后到达y的
对于这种点他们的入度和出度都是属于可以转移的
(相当于将这些点从图中取出,然后再加入图中,但是每次的取出加入可能又会导致新的取出加入的需求,然后就无限了
(也许可以拿个字典记录,不过好累,以及想了有快一个月了,再想下去就没饭吃了)...)

"""
import sys
import heapq


nodes = {} # [x][y]: [price, machine, k] 所有设备的图案
reNodes = {} # [y][x]
nodes2 = {}
x2y = {} # ["x->y"]:[(p1,p2,p3)] 缓存任意两点间的所有路径 
allMachines = [] #[(price, x, y, machine),] 按价格升序排列
g,rg = {}, {}
stat = [set(), set(), set()] # usedPoints, pointsFromUsedTo, pointsPointToUsedPoints

def selectPoint(point):
	stat[0] = set([point])
	stat[1] = set(nodes[point].keys())
	stat[2] = set(reNodes[point].keys())

def addPath(path, g=g, rg=rg):
	x, y = path
	if g.get(x) and g[x].get(y): return False
	print "connect: %s->%s" % path


	if not g.get(x): g[x] = {}
	g[x][y] = True

	if not rg.get(y): rg[y] = {}
	rg[y][x] = True
	return True

def removePath(path, g=g, rg=rg):
	x, y = path
	if g.get(x) and g[x].get(y):
		print "deconnect: %s≈%s" % path
		del g[x][y]
		del rg[y][x]
		return True
	return False

def findPath(x, prepoints, y, h, without):
	if x==without or x in prepoints: return
	prepoints.append(x)
	if x == y:
		h.append(prepoints)
		return
	for k in g[x].keys():
		findPath(k, prepoints[:], y, h, without)
def _hasAnother(x, y):
	h = []
	findPath(x, [], y, h)
	for pathPoints in h:
		if len(pathPoints) >2:
			return True
	return False

def clear(point):
	# 检查point的入度和出度是否有冗余边
	pKeysIn = rg[point].keys()
	pKeysOut = g[point].keys()
	change = set()
	if len(pKeysIn)>=2:
		for x in pKeysIn:
			if _hasAnother(x, point):
				if removePath((x, point)):
					change.add((x,point))
	if len(pKeysOut) >=2:
		for x in pKeysOut:
			if _hasAnother(point, x):
				if removePath((point, x)):
					change.add((point, x))
	return change
def clearPath(x,y):
	# 检测是否有非直接连线的x到y的连线,如果有则删除x->y
	if _hasAnother(x,y):
		removePath((x,y))

def hasPath(x, y, without):
	# 检查是否能从x 到y
	h = []
	findPath(x, [], y, h, without)
	if h:
		return True
	return False

def copyG():
	nG = {}
	nrG= {}
	for x in g.keys():
		for y in g[x].keys():
			if not nG.get(x): nG[x] = {}
			nG[x][y] = True
			if not nrG.get(y): nrG[y] = {}
			nrG[y][x] = True
	return nG,nrG
def adjustX1output((x1,y1,y2), x1Output, nG, nrG):
	# x 的ouput 可以转移到x->y1->y-> 以及x的可达线路上的任何一点出发, 如果已经在可达线路上了,那么则可以直接删除	
	for k in x1Output:
		removePath((x1,k), nG, nrG)
		h = set()
		def _findAll(x):
			if x in h:return
			h.add(x)
			for m in nG[x].keys():
				_findAll(m)
		_findAll(x1)
		if k in h: continue
		chose = None
		for m in h:
			if not nodes[m].get(k): continue
			if chose is None or chose[0] > nodes[m][k][0]:
				chose = (nodes[m][k][0], m)

		addPath((chose[1], k), nG, nrG)

def adjustY2Input((x1,y1,y2), y2Input, nG, nrG):
	# y2 的input 可以转移到y1,以及x的来路线路上的任何一点,但不能达到y自己
	for k in y2Input:
		removePath((k,y2), nG, nrG)
		h = set()
		def _findAll(x, without=[]):
			# print without
			if x in without or x in h:return
			h.add(x)
			for m in nrG[x].keys():
				_findAll(m, without)
		_findAll(y2)
		if k in h: continue
		chose = None

		# 获取k的所有来路
		h1 = h.copy()
		print h,'wow'
		for m in h1:
			if not nodes[k].get(m): continue
			# 如果在k的来路上,有连线连到m,那么当连接km 后, 该连线可以删除
			otherConnects = set()
			h.clear()
			_findAll(k, [m,y2,y1])
			for p in h:
				if nG[p].get(m):
					otherConnects.add((nodes[p][m][0], p))
			exGift = 0
			for c,p in otherConnects:
				exGift += c
			print exGift, 'wq', m, otherConnects
			if chose is None or chose[0] > nodes[k][m][0] - exGift:
				chose = (nodes[k][m][0]- exGift, m, otherConnects)
				print chose
		if chose[2]:
			for (_,p) in chose[2]:
				removePath((p, chose[1]), nG, nrG)
		addPath((k, chose[1]), nG, nrG)



def clearRedunaryPath(g=g, rg=rg):

	def findPath(x, prepoints, y, h):
		if x in prepoints: return
		prepoints.append(x)
		if x == y:
			h.append(prepoints)
			return
		for k in g[x].keys():
			findPath(k, prepoints[:], y, h)
	def _hasAnother(x, y):
		h = []
		findPath(x, [], y, h)
		for pathPoints in h:
			if len(pathPoints) >2:
				return True
		return False
	for x in g.keys():
		for y in g[x].keys():
			if _hasAnother(x, y):
				removePath((x,y), g, rg)







def collectionPaths(g=g):
	s = set()
	for x in g.keys():
		for y in g[x].keys():
			s.add((x,y))
	return s
def calPathsSum(paths):
	sum = 0
	for x,y in paths:
		print x,y
		sum += nodes[x][y][0]
	return sum

def newG((x1,y1), (x2,y2)):
	# 通过向图中添加两个路径来加入一个新点 ( x1->(y1=x2)->y2)
	# 当路径添加后,判断y2的入度能不能切换到x1,y1 然后获得更小的图
	# 当路径添加后,判断x1的出度能不能通过y1,y2出去,然后获得更小的图
	# 是否存在y2->x1的路径, 如果存在,那么y2的input转移到x1的话可以获得一份隐性资源回收(y2-x1)
	# 是否存在x1->y2的路径, 如果存在,那么可以获得一份隐性的资源回收(x1->y2)
	# x1的outpu是否可以清理
	# y2的input是否可以清理
	# (cost, addPaths, removePaths)
	# 计算可以直接去除的路线

	nG, nrG = copyG()
	y2Input, x1Output = set(nrG[y2].keys()), set(nG[x1].keys())

	# 由于有了新加入的点,所以如果存在,则必然可以回收
	addPath((x1,y1), nG, nrG)
	addPath((x2,y2), nG, nrG)
	removePath((x1,y2), nG, nrG)

	hasSuperPoint = y2Input & x1Output
	if hasSuperPoint and len(y2Input - hasSuperPoint) == 0:
		# 将super point 取出来调整它的位置
		# 意味着,super point 可以整体的替换某个路径,因为他的入口和出口都可以调整,且是在同一个环上调整
		print hasSuperPoint, '哦ih'
		for point in hasSuperPoint:
			h = []
			findPath(y2, [], x1, h, None)
			start, paths = None, []
			for points in h:
				for p in points:
					if start is not None:
						print start
						path=(start, p)
						paths.append(path)
					start = p
					print "222", start
			chose = [nodes[x1][point][0] + nodes[point][y2][0], (x1, y2)]
			print paths, h
			for x,y in paths:
				if not nodes[x].get(point): continue
				if not nodes[point].get(y): continue
				if nodes[x][point][0] + nodes[point][y][0] - nodes[x][y][0] < chose[0]:
					chose = [nodes[x][point][0] + nodes[point][y][0], (x, y)]
			removePath((x1, point), nG, nrG)
			removePath((point, y2), nG, nrG)
			addPath((chose[1][0], point), nG, nrG)
			addPath((point, chose[1][1]), nG, nrG)
		y2Input, x1Output = set(nrG[y2].keys()), set(nG[x1].keys())

	# print "计算x1 的出度的转移"
	adjustX1output((x1,y1,y2), x1Output, nG, nrG)
	# print "计算y2 的入度的转移"
	adjustY2Input((x1,y1,y2), y2Input, nG, nrG)
	# 清理图上的冗余边
	clearRedunaryPath(nG, nrG)
	ps1, ps2 = collectionPaths(), collectionPaths(nG)
	needAddPath, clearPath = ps2 - ps1, ps1 - ps2
	# print needAddPath
	# print clearPath
	sum = calPathsSum(needAddPath) - calPathsSum(clearPath)
	return (sum, needAddPath, clearPath)







def addPointToG(point):
	# print "\n%s\n" % point
	# 加入一个点,意味着,将这个点的入度出度连接到图上
	selectOutput = stat[0] & set(nodes[point].keys())
	selectInput  = stat[0] & set(reNodes[point].keys())

	pairs = None # (cost, addPaths, removePaths)
	# print selectInput, selectOutput
	# print "$" * 20
	for x in selectInput:
		for y in selectOutput:
			# x->point, point->y
			# 并且检查y的入度,能否通过连接到x 或者连接到point来获益
			# 并且检查x的出度能否变为通过point或者y出去来获益
			# print "*" * 20
			# print "==", x, point, y
			pairs2 = newG((x,point), (point, y))
			# print pairs2, "\n\n\n"
			if pairs is None or pairs[0] > pairs2[0]:
				pairs = pairs2
	# print "wwww", pairs
	for path in pairs[1]:
		addPath(path)
	for path in pairs[2]:
		removePath(path)
	updateStat()




def updateStat():
	stat[:] = [set(), set(), set()]
	for x in g.keys():
		stat[0].add(x)
		for y in g[x].keys():
			stat[0].add(y)
	for x in stat[0]:
		for y in nodes[x].keys():
			if y not in stat[0]:
				stat[1].add(y)
		for y in reNodes[x].keys():
			if y not in stat[0]:
				stat[2].add(y)
def addMiniCycle(path):
	# 从某一路径出发找出过这条路径的最小环,加入图中
	def _findShortestPath(x, y):
		item = (0, [x])
		h = [item]
		while True:
			lastPrice, prepoints = heapq.heappop(h)
			k = prepoints[-1]
			if k == y: break
			for k2,(price, _,_) in nodes[k].items():
				points = prepoints[:]
				points.append(k2)
				heapq.heappush(h, (lastPrice + price, points))
		start = None
		paths = []
		for x in prepoints:
			if start is not None:
				paths.append((start, x))
			start = x
		return paths

	x,y = path
	paths2 = _findShortestPath(y,x)
	paths2.append(path)
	for path in paths2:
		addPath(path)
	# 更新出度和入度
	updateStat()



def notStable():
	change = False
	# 对所有图中单入口单出口的点
	# 将其取出,然后再加入,看改点的入度出度是否相同
	l = []
	for p in stat[0]:
		if len(g[p].keys()) == 1 and len(rg[p].keys()) == 1:
			l.append((p, rg[p].keys()[0], g[p].keys()[0]))
	for (p, input, output) in l:
		if nodes[input].get(output):
			removePath((input,p))
			removePath((p, output))
			addPath((input, output))
			addPointToG(p)
			if rg[p].keys() != [input] or g[p].keys() != [output]:
				return True
	return change


def miniCycle():
	(_, x, y, _) = allMachines[0]
	addMiniCycle((x,y))

	while stat[1] or stat[2]:
		# 点的两端(出入)都连在图上
		intersect = stat[1] & stat[2]
		if not intersect:
			# 将出度中的一点和点集的最近一点 连成一条路径
			# 然后从这条路径出发找出一个回到图中的最短路径,加入进来;
			# 然后更新出度和入度
			# pass
			print "没碰到过..."
			break
		else:
			# 取出相交的一点
			h = []
			p = list(intersect)[0]
			addPointToG(p)
	# 接下来对图中单入口,单出口的点,取出,然后再加入,看图是否变化,如果变化说明不是最优
	while notStable():pass
	calGSum()

def calGSum():
	sum = 0
	h = []
	for x in g.keys():
		for y in g[x].keys():
			sum += nodes[x][y][0]
			heapq.heappush(h, int(nodes[x][y][1][1:]))
	print sum
	h2 = []
	while h:
		x = heapq.heappop(h)
		h2.append(str(x))
	print " ".join(h2)

def hashSet(pointSet):
	h = []
	for x in pointSet:
		heapq.heappush(h, x)
	return "".join(h)

def flody():
	keys = nodes.keys()
	for k in keys:
		for x in keys:
			if x == k:continue
			for y in nodes[x].keys():
				if y == k or y==x:continue
				if not nodes[x].get(k) or not nodes[k].get(y):continue
				sum = nodes[x][k][0] + nodes[k][y][0]				
				if nodes[x][y][0] > sum:
					nodes[x][y] = [nodes[x][y][0], None, k]

def clearRedunary():
	keys = nodes.keys()
	for x in keys:
		for y in nodes[x].keys():
			if nodes[x][y][2] is not None:
				# print "clean %s->%s k: %s" % (x,y, nodes[x][y][2])
				del nodes[x][y]

def findAllX2YPathsPointsle3():
	# x2y = {} # ["x->y"]:[(p1,p2,p3)] 缓存任意两点间的所有路径 	
	def _findx2y(x,y):
		h = set()
		def __findx2y(x, prepoints, y):
			if len(prepoints) >= 3: return
			if x in prepoints: return
			prepoints.append(x)
			if x == y:
				h.add(tuple(prepoints))
				return
			for k in nodes[x].keys():
				__findx2y(k, prepoints[:], y)
		__findx2y(x, [], y)
		xy = "%s->%s" % (x,y)
		x2y[xy] = h
	allPoints = set()
	for x in nodes.keys():
		allPoints.add(x)
		for y in nodes[x].keys():
			allPoints.add(y)
	keys = list(allPoints)
	for x in keys:
		for y in keys:
			if x == y: continue
			_findx2y(x,y)


def process():
	# # 求出任意两点间的最短距离
	flody()
	# 剔除冗余路线,如果Sxy  <   Sxk + Sky 那么删除x->y
	clearRedunary()
	copyPriceAndInitReNodes()
	# outputCleanMachine()
	# 计算并缓存任意两点间的所有路径
	findAllX2YPathsPointsle3()	
	miniCycle()

def outputCleanMachine():
	for x in nodes.keys():
		for y in nodes[x].keys():
			print nodes[x][y][1], x, y, nodes[x][y][0]

def copyPriceAndInitReNodes():
	for x in nodes.keys():
		for y in nodes[x].keys():
			nodes[x][y] = [nodes2[x][y][0], nodes2[x][y][1], None]
			if not reNodes.get(y):
				reNodes[y] = {}
			reNodes[y][x] = True

def output():
	sum = 0
	machine = []
	for start in nodes.keys():
		for end in nodes[start].keys():
			sum += nodes[start][end][0]
			machineName = nodes[start][end][1][1:]
			hadBeenInsert = False
			for index,name in enumerate(machine):
				if int(machineName) < int(name):
					machine.insert(index, machineName)
					hadBeenInsert = True
					break
			if not hadBeenInsert:
				machine.append(machineName)

	print sum
	print " ".join(machine)
	pass

def initDataFromFile(f):
	for line in f:
		line = line.replace("\t", " ").split()
		# from, to, price, machineName
		machineName = line[0]
		x = line[1]
		y = line[2]
		price = int(line[3])

		if not nodes.get(x):
			nodes[x] = {}
		nodes[x][y] = [price, machineName, None]
		if not nodes2.get(x):
			nodes2[x] = {}
		nodes2[x][y] = [price, machineName, None]

		heapq.heappush(allMachines, (price, x,y, machineName))
		# allMachines.append((price,x,y,machineName))
def log(str):
	# print str
	pass

def main(f):
	# 初始化数据
	# 计算任意两点的最短距离
	# 处理图
	# 输出结果
	initDataFromFile(f)
	log("init finish")
	process()
	log("process finish")
	# output()
	log("output finish")

if __name__ == '__main__':
	import sys
	filename = sys.argv[1]
	f = open(filename)
	main(f)
	f.close()