last one in http://icpc.baylor.edu/icpc/Finals/2007WorldFinalProblemSet.pdf

please initiate the discussion, then everyone 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?

Let 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.

The tunnel can be bombed at any time.

I didn't read the question carefully.

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

是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.

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, 然后等一下。可以更好一些。

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.

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;

You are right. My algorithm does not work for your case.

Let me think about it further.

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)吧。

u then destroy the tunnel from 2 to 0, he can still go back to 1, and choose aon of 3 or 4

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.

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;