这样可以么?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
似乎还是不行
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, 然后等一下。可以更好一些。
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, 然后等一下。可以更好一些。