似乎还是不行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.
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.
Huasing Association 1999 - 2013