这样可以么？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
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;
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;
Huasing Association 1999 - 2013