这题真不是盖的，要是不看解题报告，恐怕一辈子都做不出来啦。。
题目直接就是要解决一个叫做“最大密度子图的问题”。
就是在一简单图里面找出n个点，这n个点之间有m条边，让m/n最大。
这种问题还是有点实际意义的。
算法很复杂，找了一份高中生巨牛写的文档（90后真不是盖的）。http://wenku.baidu.com/view/986baf00b52acfc789ebc9a9.html
。
该文档描述了一系列的最小割算法，其中包括这个“最大密度子图问题”。
我编码能力差，不想写c代码，写了一个py的脚本，能过官方数据，就是速度巨慢，开了一分钟也没跑完。。
import sys
def dinic(N, S, T, caps):
to = []
cap = []
head = [[] for i in range(N)]
d = [-1]*N
ans = 0
cut = set()
for a, b, c in caps:
head[a].append(len(cap))
cap.append(c)
to.append(b)
head[b].append(len(cap))
cap.append(0)
to.append(a)
def build():
for i in range(N):
d[i] = -1
q = [S]
d[S] = 0
cut.clear()
while len(q):
x = q[0]
del q[0]
for i in head[x]:
y = to[i]
if cap[i] and d[y] == -1:
d[y] = d[x] + 1
if y == T:
return 1
q.append(y)
cut.add(y)
return 0
def find(x, low):
if x == T:
return low
for i in head[x]:
y = to[i]
if cap[i] and d[y] == d[x] + 1:
f = find(y, min(low, cap[i]))
if f:
cap[i] -= f
cap[i^1] += f
return f
return 0
while build():
while 1:
f = find(S, sum(cap))
if f == 0:
break
ans += f
return ans, cut
def max_weight_closure(V, edges):
inf = sum([abs(i) for i in V])
caps = [(a,b,inf) for a,b in edges]
S = len(V)
T = S + 1
for i in range(len(V)):
if V[i] > 0:
caps.append((S,i,V[i]))
elif V[i] < 0:
caps.append((i,T,-V[i]))
flow, cut = dinic(len(V)+2, S, T, caps)
return sum([V[i] for i in cut]), cut
def max_density_subgraph(N, edges):
def solve(g):
V = [-g]*N
E = []
for u,v in edges:
ve = len(V)
E += [(ve,u), (ve,v)]
V.append(1)
w, cut = max_weight_closure(V, E)
if len(cut) == 0:
w = -1
return w, cut
l = 1.0/N
r = len(edges)
while l < r - 0.01:
m = (l + r) / 2
if solve(m)[0] < 0:
r = m
else:
l = m
w, cut = solve(l)
l = [ i for i in cut if i < N]
if len(l) == 0:
l = [0]
return l
def get_density(N, edges, sel):
e = float(len([1 for a,b in edges if a in sel and b in sel]))
return e/float(len(sel))
fi = open('3155.in')
fo = open('3155.out')
g = lambda x : [ int(i) for i in x.readline().split(' ') ]
ti = 0
while 1:
l = g(fi)
if len(l) == 0:
break
N, M = l
print '----', ti
print 'N M', N, M
E = [ [j-1 for j in g(fi)] for i in range(M)]
cut = max_density_subgraph(N, E)
k = g(fo)[0]
ans = [g(fo)[0]-1 for i in range(k)]
d_ans = get_density(N, E, ans)
d_mine = get_density(N, E, cut)
print 'mine', d_mine
print 'ans', d_ans
if abs(d_ans - d_mine) > 0.001:
print 'error'
break
ti += 1