关于连通图的问题,这道题我直接连题目都看不懂。。。请教大神。。。
Jo has been having “issues” lately with the network, since it seems at times as though portions of it are disconnected, or “blankety-blank close to being disconnected,” as she so colorfully puts it. In particular, she wonders what is the fewest number of edges that could to be zapped so that there would be no paths between
her node and Hal’s.
Come up with a way for her to find the “Jo-Hal connectivity” of the network, given a description of the network layout.
Design a fast algorithm to do this, and analyze its speed. And do hurry, because her ultimate happiness may hang
in the balance!
大致意思好像是Jo和Hal分别有一个NODE,Jo想知道最少要去掉多少掉边才能让他的NODE和Hal的NODE之间没有通路。
[解决办法]
裸的最小割。
[解决办法]
有向图的有向路径
[解决办法]
求出每条路
R1:L1,L2,L3;
R2:L4,L2,L3.
R1+R2 = L1+2*L2+2*L3+L4
由于L2和L3的系数最大(为2,其他路均为1),所以去掉其中任一条,并计数1
重复以上步骤,知道找不到通路,计数值为N
N即为所求