anyone interested to discuss about the last question in ACM this year? (more...)
min-cut problem?
please initiate the discussion, then everyone follows.
min-cut problem?
anyone interested to discuss about the last question in ACM this year? (more...)
construct a graph as follows
vertices: from 0 to n, n+1 vertices, where 0 is outside
edges: weight of edge = number of tunnel connecting the two vertices
perform standard max-flow algorithm
is that right?
edges: weight of edge = number of tunnel connecting the two vertices
perform standard max-flow algorithm
is that right?
construct a graph as followsvertices: from 0 to n, n+1 vertices, where 0 is outside
edges: weight of edge = number of tunnel connecting the two vertices
perform standard max-flow algorithm
is that right?
maxflow from vertex 0 to vertex 1
disagreeLet the edges being:
1 2
2 0
1 3
3 0
1 4
4 0
is the max-flow 3? if true, then disagree since we can wait until the spy enter one of 2, 3 or 4.
so assume the spy enters 2
u then destroy the tunnel from 2 to 0, he can still go back to 1, and choose aon of 3 or 4
so assume the spy enters 2u then destroy the tunnel from 2 to 0, he can still go back to 1, and choose aon of 3 or 4
choose one of 3 or 4
i think we can destroy the tunnels 2 0 and 2 1 simultaneously.
ok, i misunderstood the problem
华新中文网致力于为新加坡留学生、工作人士及华人同胞提供交流空间和服务平台
关于我们┊ 广告服务┊ 联系方式┊ 华新博客┊ 经典怀旧┊ 投递作品
Huasing Association 1999 - 2013
