anyone interested to discuss about the last question in ACM this year? <Tunnelslast one in http://icpc.baylor.edu/icpc/Finals/2007WorldFinalProblemSet.pdf[chancing (9-6 9:59, Long long ago)] [ 传统版 | sForum ][登录后回复]1楼

min-cut problem?please initiate the discussion, then everyone follows.[icky (9-6 12:33, Long long ago)] [ 传统版 | sForum ][登录后回复]2楼

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?[icky (9-7 18:16, Long long ago)] [ 传统版 | sForum ][登录后回复]3楼

(引用 icky:construct a graph as followsvertices: from 0 to n, n+1 vertices, where 0 is outside edges: weight of edge = number of tunnel co...)maxflow from vertex 0 to vertex 1[icky (9-7 18:17, Long long ago)] [ 传统版 | sForum ][登录后回复]4楼

(引用 icky:construct a graph as followsvertices: from 0 to n, n+1 vertices, where 0 is outside edges: weight of edge = number of tunnel co...)agree[吴永铮 (9-12 15:07, Long long ago)] [ 传统版 | sForum ][登录后回复]5楼

(引用 icky:construct a graph as followsvertices: from 0 to n, n+1 vertices, where 0 is outside edges: weight of edge = number of tunnel co...)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.[bugzzj (9-20 15:35, Long long ago)] [ 传统版 | sForum ][登录后回复]6楼

(引用 bugzzj: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 th)opps! you are right.The tunnel can be bombed at any time.

I didn't read the question carefully.[吴永铮 (9-20 16:25, Long long ago)] [ 传统版 | sForum ][登录后回复]7楼

这样可以么？for each node v

perform a maximal flow between v and 0 to obtain the minimal cut (=mc);

set the key of v to mc and insert it into a Fibonacci heap h;

end

while(true)

v = h.extract_min(); (based on the key)

remove v and all edges incident on v;

if(node 1 is disconnected from node 0)

return v.key;

end
end[房间 (9-20 21:03, Long long ago)] [ 传统版 | sForum ][登录后回复]8楼

(引用 房间:这样可以么？for each node v perform a maximal flow between v and 0 to obtain the minimal cut (=mc); set the key of v t...)顺带询问一个问题是CLRS page 216 10.4-5


Write an O(n)-time nonrecursive procedure that, given an n-node binary tree, prints out the key of each node. Use no more than constant extra space outside of the tree itself and do not modify the tree, even temporarily, during the procedure.[房间 (9-20 21:19, Long long ago)] [ 传统版 | sForum ][登录后回复]9楼

(引用 房间:这样可以么？for each node v perform a maximal flow between v and 0 to obtain the minimal cut (=mc); set the key of v t...)似乎还是不行1 2
2 0
1 3
3 0
1 4
4 0
1 5
5 0
5 0
5 0
5 0

对min-cut不是很清楚，下面的计算对吗？
MC(1)=4
MC(2)=2
MC(3)=2
MC(4)=2
MC(5)=5

如果是对的，根据你的算法，结果应该是MC(1)=4吧？
不过，先断掉edge 1 5, 然后等一下。可以更好一些。[bugzzj (9-21 10:29, Long long ago)] [ 传统版 | sForum ][登录后回复]10楼

(引用 bugzzj:似乎还是不行1 2 2 0 1 3 3 0 1 4 4 0 1 5 5 0 5 0 5 0 5 0 对min-cut不是很清楚，下面的计算对吗？ MC(1)=4 MC(2)=2 MC(3)=2 MC(4)=2 ...)是可以的In your case:

MC(1) = 3;
MC(2) = 2;
MC(3) = 1;
MC(4) = 2;
MC(5) = 5;

min cut means the minimal number of cuts to disconnect the source node from the sink node, so for node 1, we only need to cut the following edges:
(1, 5), (2, 0), (4, 0). Of course there are some other minimal cuts.

Accoring to my algorithm, it will output 3.

According to what you have said, you want to first cut (1, 5), then the spy has only two paths to escape, namely, through node 2 and through node 4. For the path that bypasses node 2, you have to wait until the spy has entered room 2, then you need to cut (1, 2) and (2, 0), which incurs two cuts, so in total, it's three cuts. Similarly for the path through node 4.

If you cut (1, 5) in the first place, and then wait until the spy has entered room 2, and you only cut (2, 0), then the spy can turn back to choose the path that goes through node 4. So you still need to cut (1, 4) or (4, 0). In this case, you again need three cuts, which matches the output of my algorithm.

[房间 (9-21 11:32, Long long ago)] [ 传统版 | sForum ][登录后回复]11楼

(引用 房间:是可以的In your case: MC(1) = 3; MC(2) = 2; MC(3) = 1; MC(4) = 2; MC(5) = 5; min cut means the minimal number of cuts to...)看错了Sorry I overlooked the edge (3, 0) in your specification. So the min cuts of each node are indeed:

MC(1) = 4;
MC(2) = 2;
MC(3) = 2;
MC(4) = 2;
MC(5) = 5;[房间 (9-21 11:38, Long long ago)] [ 传统版 | sForum ][登录后回复]12楼

(引用 房间:看错了Sorry I overlooked the edge (3, 0) in your specification. So the min cuts of each node are indeed: MC(1) = 4; MC(2) = 2; ...)AndYou are right. My algorithm does not work for your case.

Let me think about it further.[房间 (9-21 11:40, Long long ago)] [ 传统版 | sForum ][登录后回复]13楼

(引用 房间:顺带询问一个问题是CLRS page 216 10.4-5 Write an O(n)-time nonrecursive procedure that, given an n-node binary tree, prints out...)如果child有到parent的ref的话。Let
struct treeNode{
int id;
treeNode *left;
treeNode *right;
treeNode *par;
};

DFS(treeNode *root){
treeNode *cur=root;
while (cur!=NULL){
printf("%d, ", cur->id);
if (cur->left!=NULL){
cur=cur->left;
}
else if (cur->right!=NULL)
cur=cur->right;
else{
treeNode *par=cur->par;
while (par!=NULL){
if (par->left==cur && par->right!=NULL){
cur=par->right;
break;
}
cur=par;
par=par->par;
}
if (par==NULL) cur=NULL;
}
}
}

其实就是depth first, 应该是O(3n)=O(n)吧。[bugzzj (9-24 14:50, Long long ago)] [ 传统版 | sForum ][登录后回复]14楼

(引用 bugzzj: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 th)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[icky (9-24 16:14, Long long ago)] [ 传统版 | sForum ][登录后回复]15楼

(引用 icky: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[icky (9-24 16:14, Long long ago)] [ 传统版 | sForum ][登录后回复]16楼

(引用 icky: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)i think we can destroy the tunnels 2 0 and 2 1 simultaneously.[bugzzj (9-24 17:21, Long long ago)] [ 传统版 | sForum ][登录后回复]17楼

(引用 bugzzj:i think we can destroy the tunnels 2 0 and 2 1 simultaneously.)ok, i misunderstood the problem[icky (9-25 9:49, Long long ago)] [ 传统版 | sForum ][登录后回复]18楼

(引用 bugzzj:如果child有到parent的ref的话。Let struct treeNode{ int id; treeNode *left; treeNode *right; treeNode *par; }; DFS(treeNode ...)gr8.When I was asking for the answer, I didn't presume there is a parent link in each node, though. However, I guess the parent link is necessary.[房间 (10-16 1:02, Long long ago)] [ 传统版 | sForum ][登录后回复]19楼

(引用 房间:这样可以么？for each node v perform a maximal flow between v and 0 to obtain the minimal cut (=mc); set the key of v t...)I have revised the solution.for each node, store a number which is initialized to be the number of edges incident on that node. For node 0 (which represents outside), the number is infinity. we denote the number as node.mc.


changed = true;
while(changed)
{
changed = false;
for_each(node n in the graph except node 0)
{
sort n's adjacent nodes based on mc (from large to small).
k = 0; k1 = 0; prev_node = null;
for_each(node adj_n in the sorted adjacent nodes n)
{
if(adj_n.mc + k < n.mc)
{
n.mc = k + adj_n.mc;
changed = true;
}
k1 += number of edges between adj_n and n;
if(prev_node.mc > adj_n.mc)
{
k = k1;
}
prev_node = adj_n;
}
}
}

return node1.mc;[房间 (10-16 1:15, Long long ago)] [ 传统版 | sForum ][登录后回复]20楼