鎻忚堪錛?/strong>鍦ㄥ浜庝換閫変竴涓浘涓粨鐐逛負鏍圭殑DFS鎼滅儲鏍戜腑寤虹珛涓涓狶AB鏁扮粍涓嶭OW鏁扮粍錛孡AB鏁扮粍瀛樺偍涓粨鐐圭殑緙栧彿錛孡OW鏁扮粍瀛樺偍鍚勭偣鍙婂叾瀛愭爲鐨勫悇緇撶偣鑳藉埌杈劇殑鏈灝忕紪鍙風粨鐐圭殑緙栧彿銆?br>
1 //lab涓轟竴涓叏灞鍙橀噺錛屽垵濮嬩負1錛?nbsp;LAB鍚勯」鍒濆涓?
2 DFS(u)
3 LAB[u] = LOW[u] = lab++
4 for each (u, v) in E(G)
5 if LAB[v] is 0
6 DFS(v)
7 LOW[u] = min{LOW[u], LOW[v]}
8 else if v isnot parent of u
9 LOW[u] = min{LOW[u], LAB[v]}
2 DFS(u)
3 LAB[u] = LOW[u] = lab++
4 for each (u, v) in E(G)
5 if LAB[v] is 0
6 DFS(v)
7 LOW[u] = min{LOW[u], LOW[v]}
8 else if v isnot parent of u
9 LOW[u] = min{LOW[u], LAB[v]}
絎?琛屼腑錛屽鏋?u, v)鏄爲杈癸紝鍒欏v鍋氭繁搴︿紭鍏堟悳绱紝騫朵笖LOW[u] = min{LOW[u], LOW[v]}錛屽鏋?u, v)鏄弽鍚戣竟錛屽垯LOW[u] = min{LOW[u], LAB[v]}銆?/span>
涓夈佸壊鐐?br> 鎻忚堪錛?/strong>褰撲竴涓粨鐐箄鏄壊鐐規椂蹇呮弧瓚充互涓嬩袱涓潯浠朵箣涓錛?br> 1錛塽涓烘牴涓旇嚦灝戞湁涓ゆ５瀛愭爲錛?br> 2錛塽涓嶄負鏍逛笖瀛樺湪涓涓猽鍦ㄦ繁鎼滄爲涓殑瀛愬コv浣垮緱LOW[v] ≥ LAB[u]銆?br> 紺轟緥錛?/strong>POJ 1523 瑙ｉ鎶ュ憡銆?br>鍥涖佹ˉ
鎻忚堪錛?/strong>涓鏉¤竟e=(u, v)鏄ˉ錛屽綋涓斾粎褰揺涓烘爲鏋濊竟涓擫OW[v] > LAB[u]銆?br> 紺轟緥錛?/strong>POJ 3352 瑙ｉ鎶ュ憡銆?/span>
]]>
Description
Consider the two networks shown below. Assuming that data moves around these networks only between directly connected nodes on a peer-to-peer basis, a failure of a single node, 3, in the network on the left would prevent some of the still available nodes from communicating with each other. Nodes 1 and 2 could still communicate with each other as could nodes 4 and 5, but communication between any other pairs of nodes would no longer be possible.
Node 3 is therefore a Single Point of Failure (SPF) for this network. Strictly, an SPF will be defined as any node that, if unavailable, would prevent at least one pair of available nodes from being able to communicate on what was previously a fully connected network. Note that the network on the right has no such node; there is no SPF in the network. At least two machines must fail before there are any pairs of available nodes which cannot communicate.
Node 3 is therefore a Single Point of Failure (SPF) for this network. Strictly, an SPF will be defined as any node that, if unavailable, would prevent at least one pair of available nodes from being able to communicate on what was previously a fully connected network. Note that the network on the right has no such node; there is no SPF in the network. At least two machines must fail before there are any pairs of available nodes which cannot communicate.
Input
The input will contain the description of several networks. A network description will consist of pairs of integers, one pair per line, that identify connected nodes. Ordering of the pairs is irrelevant; 1 2 and 2 1 specify the same connection. All node numbers will range from 1 to 1000. A line containing a single zero ends the list of connected nodes. An empty network description flags the end of the input. Blank lines in the input file should be ignored.
Output
For each network in the input, you will output its number in the file, followed by a list of any SPF nodes that exist.
The first network in the file should be identified as "Network #1", the second as "Network #2", etc. For each SPF node, output a line, formatted as shown in the examples below, that identifies the node and the number of fully connected subnets that remain when that node fails. If the network has no SPF nodes, simply output the text "No SPF nodes" instead of a list of SPF nodes.
The first network in the file should be identified as "Network #1", the second as "Network #2", etc. For each SPF node, output a line, formatted as shown in the examples below, that identifies the node and the number of fully connected subnets that remain when that node fails. If the network has no SPF nodes, simply output the text "No SPF nodes" instead of a list of SPF nodes.
Sample Input
1 2 5 4 3 1 3 2 3 4 3 5 0 1 2 2 3 3 4 4 5 5 1 0 1 2 2 3 3 4 4 6 6 3 2 5 5 1 0 0
Sample Output
Network #1 SPF node 3 leaves 2 subnets Network #2 No SPF nodes Network #3 SPF node 2 leaves 2 subnets SPF node 3 leaves 2 subnets
浜屻佸垎鏋?br> 鐢―FS瑙ｅ喅闂錛岃緇嗙畻娉曪細鍓茬偣涓庢ˉ銆?/span>
涓夈佷唬鐮?br>
1
#include<iostream>
2#include<list>
3using namespace std;
4int t;
5int v1, v2;
6list<int> g[1001];
7bool flag;
8int root;
9int counter;
10bool spf[1001];
11int low[1001], lab[1001];
12bool visit[1001];
13void dfs(int u, int fa)
14
{
15
low[u] = lab[u] = counter++;
16 list<int>::iterator it;
17 int counter = 0;
18 for(it = g[u].begin(); it != g[u].end(); it++)
19
{
20 int v = *it;
21 if(!lab[v])
22 {
23 counter++;
24 dfs(v, u);
25 low[u] = min(low[u], low[v]);
26 if((u==root && counter>=2) || (u!=root && low[v]>=lab[u]))
27 spf[u] = flag = true;
28
}
29 else if(v != fa)
30 low[u] = min(low[u], lab[v]);
31 }
32
}
33void find(int u)
34{
35 visit[u] = true;
36 list<int>::iterator it;
37 for(it = g[u].begin(); it != g[u].end(); it++)
38 if(!visit[*it])
39 find(*it);
40}
41int main()
42{
43 t = 1;
44 while(1)
45 {
46 scanf("%d", &v1);
47 if(v1 == 0) break;
48 for(int i=1; i<=1000; i++)
49 g[i].clear();
50 memset(spf, 0, sizeof spf);
51 memset(low, 0, sizeof low);
52 memset(lab, 0, sizeof lab);
53 while(v1 != 0)
54 {
55 scanf("%d", &v2);
56 g[v1].push_back(v2);
57 g[v2].push_back(v1);
58 root = v1;
59 scanf("%d", &v1);
60 }
61 counter = 1;
62 flag = false;
63 dfs(root, -1);
64 printf("Network #%d\n", t++);
65 if(flag)
66 {
67 for(int i=1; i<=1000; i++)
68 {
69 if(!spf[i]) continue;
70 int cnt = 0;
71 memset(visit, 0, sizeof visit);
72 visit[i] = true;
73 list<int>::iterator it;
74 for(it = g[i].begin(); it != g[i].end(); it++)
75 if(!visit[*it])
76 {
77 cnt++;
78 find(*it);
79 }
80 printf(" SPF node %d leaves %d subnets\n", i, cnt);
81 }
82 }
83 else
84 printf(" No SPF nodes\n");
85 printf("\n");
86 }
87}
#include<iostream>2
#include<list>3
using namespace std;4
int t;5
int v1, v2;6
list<int> g[1001];7
bool flag;8
int root;9
int counter;10
bool spf[1001];11
int low[1001], lab[1001];12
bool visit[1001];13
void dfs(int u, int fa)14
{15
low[u] = lab[u] = counter++;16
list<int>::iterator it;17
int counter = 0;18
for(it = g[u].begin(); it != g[u].end(); it++)19
{20
int v = *it;21
if(!lab[v])22
{23
counter++;24
dfs(v, u);25
low[u] = min(low[u], low[v]);26
if((u==root && counter>=2) || (u!=root && low[v]>=lab[u]))27
spf[u] = flag = true;28
}29
else if(v != fa)30
low[u] = min(low[u], lab[v]);31
}32
}33
void find(int u)34
{35
visit[u] = true;36
list<int>::iterator it;37
for(it = g[u].begin(); it != g[u].end(); it++)38
if(!visit[*it])39
find(*it);40
}41
int main()42
{43
t = 1;44
while(1)45
{46
scanf("%d", &v1);47
if(v1 == 0) break;48
for(int i=1; i<=1000; i++)49
g[i].clear();50
memset(spf, 0, sizeof spf);51
memset(low, 0, sizeof low);52
memset(lab, 0, sizeof lab);53
while(v1 != 0)54
{55
scanf("%d", &v2);56
g[v1].push_back(v2);57
g[v2].push_back(v1);58
root = v1;59
scanf("%d", &v1);60
}61
counter = 1;62
flag = false;63
dfs(root, -1);64
printf("Network #%d\n", t++);65
if(flag)66
{67
for(int i=1; i<=1000; i++)68
{69
if(!spf[i]) continue;70
int cnt = 0;71
memset(visit, 0, sizeof visit);72
visit[i] = true;73
list<int>::iterator it;74
for(it = g[i].begin(); it != g[i].end(); it++)75
if(!visit[*it])76
{77
cnt++;78
find(*it);79
}80
printf(" SPF node %d leaves %d subnets\n", i, cnt);81
}82
}83
else84
printf(" No SPF nodes\n");85
printf("\n");86
}87
}]]>
Problem Description
There are n houses in the village and some bidirectional roads connecting them. Every day peole always like to ask like this "How far is it if I want to go from house A to house B"? Usually it hard to answer. But luckily int this village the answer is always unique, since the roads are built in the way that there is a unique simple path("simple" means you can't visit a place twice) between every two houses. Yout task is to answer all these curious people.
Input
First line is a single integer T(T<=10), indicating the number of test cases.
For each test case,in the first line there are two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses and the number of queries. The following n-1 lines each consisting three numbers i,j,k, separated bu a single space, meaning that there is a road connecting house i and house j,with length k(0<k<=40000).The houses are labeled from 1 to n.
Next m lines each has distinct integers i and j, you areato answer the distance between house i and house j.
For each test case,in the first line there are two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses and the number of queries. The following n-1 lines each consisting three numbers i,j,k, separated bu a single space, meaning that there is a road connecting house i and house j,with length k(0<k<=40000).The houses are labeled from 1 to n.
Next m lines each has distinct integers i and j, you areato answer the distance between house i and house j.
Output
For each test case,output m lines. Each line represents the answer of the query. Output a bland line after each test case.
Sample Input
2 3 2 1 2 10 3 1 15 1 2 2 3 2 2 1 2 100 1 2 2 1
Sample Output
10 25 100 100
浜屻佸垎鏋?br> 鐢═arjan瑙ｅ喅鐨凩CA闂錛岃緇嗙畻娉曪細LCA闂銆?/span>
涓夈佷唬鐮?/p>
1
#include<iostream>
2#include<list>
3using namespace std;
4struct node
5{
6 int v, d;
7 void init(int vv, int dd) {v = vv; d = dd;};
8};
9int t, n, m, v1, v2, len;
10list<node> g[40001];
11list<node> query[40001];
12int dis[40001];
13int res[201][3];
14int parent[40001];
15bool visit[40001];
16int find(int k)
17{
18 if(parent[k] == k)
19 return k;
20 return parent[k] = find(parent[k]);
21}
22void tarjan(int u)
23{
24 if(visit[u]) return;
25 visit[u] = true;
26 parent[u] = u;
27 list<node>::iterator it = query[u].begin();
28 while(it != query[u].end())
29 {
30 if(visit[it->v])
31 res[it->d][2] = find(it->v);
32 it++;
33 }
34 it = g[u].begin();
35 while(it != g[u].end())
36 {
37 if(!visit[it->v])
38 {
39 dis[it->v] = min(dis[it->v], dis[u] + it->d);
40 tarjan(it->v);
41 parent[it->v] = u;
42 }
43 it++;
44 }
45}
46int main()
47{
48 scanf("%d", &t);
49 while(t--)
50 {
51 scanf("%d%d", &n, &m);
52 for(int i=1; i<=n; i++)
53 g[i].clear();
54 for(int i=1; i<=m; i++)
55 query[i].clear();
56 for(int i=1; i<n; i++)
57 {
58 scanf("%d%d%d", &v1, &v2, &len);
59 node n1; n1.init(v2, len);
60 g[v1].push_back(n1);
61 node n2; n2.init(v1, len);
62 g[v2].push_back(n2);
63 }
64 for(int i=1; i<=m; i++)
65 {
66 scanf("%d%d", &v1, &v2);
67 res[i][0] = v1;
68 res[i][1] = v2;
69 node n1; n1.init(v2, i);
70 query[v1].push_back(n1);
71 node n2; n2.init(v1, i);
72 query[v2].push_back(n2);
73 }
74 memset(visit, 0, sizeof(visit));
75 memset(dis, 0x7f, sizeof(dis));
76 dis[1] = 0;
77 tarjan(1);
78 for(int i=1; i<=m; i++)
79 printf("%d\n", dis[res[i][0]] + dis[res[i][1]] - 2*dis[res[i][2]]);
80 }
81}
]]>
]]>
]]>
鏈灝忚垂鐢ㄦ渶澶ф祦錛氳G鏄互s涓烘簮t涓烘眹鐨勭綉緇滐紝c鏄疓鐨勫閲忥紝b鏄疓鐨勫崟浣嶆祦閲忚垂鐢紝涓旀湁b[i][j] = -b[i][j]錛宖鏄疓鐨勬祦錛屽垯b(f)=鈭?fij*bij)錛?i, j)∈E(G) 涓攆ij>0銆傛渶灝忚垂鐢ㄦ渶澶ф祦闂錛屽氨鏄眰緗戠粶G鐨勬渶澶ф祦f涓斾嬌璐圭敤b(f)鏈灝忋傝繖鏍風殑嫻佺О涓烘渶灝忚垂鐢ㄦ渶澶ф祦銆?/span>
浜屻佺畻娉曟濇兂
鐢‵ord-Fulkerson綆楁硶鐨勬濇兂錛屼笉鏂湴鍦ㄦ畫鐣欑綉緇滀腑瀵繪壘澧炲箍璺紝鍙笉榪囪繖涓騫胯礬鏄綋鍓嶇綉緇滀腑s鍒皌鐨勪互鍗曚綅嫻侀噺璐圭敤涓烘潈鐨勬渶鐭礬錛屽榪欐潯澧炲箍璺繘琛屾搷浣溿傜敱浜庤垂鐢ㄦ湁璐熷鹼紝寤鴻鐢⊿PFA綆楁硶銆?br>涓夈佺畻娉曚粙緇?br> 鎻忚堪錛?/span>
1 MCMF(G, s, t)
2 for each edge(u, v) in E(G)
3 do f[u, v] = 0
4 f[v, u] = 0
5 while exists a path p from s to t in Gf and p is the shortest path
6 do cf(p) = min{cf(u, v) : (u, v) in p}
7 for each edge(u, v) in p
8 do f[u, v] = f[u, v] + cf(p)
9 f[v, u] = - f[u, v]
瀹炵幇錛?br>
2 for each edge(u, v) in E(G)
3 do f[u, v] = 0
4 f[v, u] = 0
5 while exists a path p from s to t in Gf and p is the shortest path
6 do cf(p) = min{cf(u, v) : (u, v) in p}
7 for each edge(u, v) in p
8 do f[u, v] = f[u, v] + cf(p)
9 f[v, u] = - f[u, v]
1mcmf()
2{
3 while(true)
4 {
5 for(int i=1; i<=n+m+1; i++)
6 d[i] = MAX;
7 d[s] = 0;
8 spfa(); //p涓瓨鏈夎鐐圭殑鍓嶇戶鐐?/span>
9 if(p[t] == -1) //琛ㄧず宸叉棤澧炲箍璺?/span>
10 break;
11 int minf = INT_MAX;
12 int it = t;
13 while(p[it] != -1)
14 {
15 minf = min(minf, c[p[it]][it] - f[p[it]][it]);
16 it = p[it];
17 }
18 it = t;
19 while(p[it] != -1)
20 {
21 f[p[it]][it] += minf;
22 f[it][p[it]] = -f[p[it]][it];
23 it = p[it];
24 }
25 }
26}
mcmf()2
{3
while(true)4
{5
for(int i=1; i<=n+m+1; i++)6
d[i] = MAX;7
d[s] = 0;8
spfa(); //p涓瓨鏈夎鐐圭殑鍓嶇戶鐐?/span>9
if(p[t] == -1) //琛ㄧず宸叉棤澧炲箍璺?/span>10
break;11
int minf = INT_MAX;12
int it = t;13
while(p[it] != -1)14
{15
minf = min(minf, c[p[it]][it] - f[p[it]][it]);16
it = p[it];17
}18
it = t;19
while(p[it] != -1)20
{21
f[p[it]][it] += minf;22
f[it][p[it]] = -f[p[it]][it];23
it = p[it];24
}25
}26
}涓夈佺畻娉曠ず渚?br> POJ 2516 瑙ｉ鎶ュ憡
]]>
]]>
鍖歸厤錛氳G(V, E)涓烘棤鐜浘錛岃M涓篍鐨勪竴涓潪絀哄瓙闆嗭紝濡傛灉M涓殑浠繪剰涓ゆ潯杈瑰湪G涓笉鐩擱偦錛屽垯縐癕鏄浘G涓殑涓涓尮閰嶃傝嫢瀵瑰浘G鐨勪換浣曞尮閰峂'錛屽潎鏈墊M'|≤|M|錛屽垯縐癕涓篏鐨勬渶澶у尮閰嶃?br> 楗卞拰鐐癸細璁綧鏄浘G涓殑鍖歸厤錛孏涓笌M涓殑杈瑰叧鑱旂殑欏剁偣縐頒負M楗卞拰鐐癸紝鍚﹀垯縐頒負M闈為ケ鍜岀偣銆傝嫢鍥句腑欏剁偣鍧囨槸M楗卞拰鐐癸紝鍒欑ОM涓篏鐨勫畬緹庡尮閰嶃?br> M浜ら敊璺細璁綪鏄疓鐨勪竴鏉¤礬錛屼笖鍦≒涓紝M鐨勮竟鍜孍-M鐨勮竟浜ら敊鍑虹幇錛屽垯縐癙鏄疓鐨勪竴鏉浜ら敊璺傝嫢M浜ら敊璺疨鐨勪袱涓鐐逛負M闈為ケ鍜岀偣錛屽垯縐癙涓篗鍙騫胯礬銆?nbsp;
鏍瑰湪x鐨凪浜ら敊瀛愬浘錛氳x涓篏涓璏闈為ケ鍜岀偣銆侴涓敱璧風偣涓簒鐨凪浜ら敊璺墍鑳借繛鎺ョ殑欏剁偣闆嗘墍瀵煎嚭鐨凣鐨勫鍑哄瓙鍥俱?br> S鐨勯偦闆嗭細璁維涓篏鐨勪換涓欏剁偣闆嗭紝G涓笌S鐨勯《鐐歸偦鎺ョ殑鎵鏈夐《鐐圭殑闆嗗悎錛岀О涓篠鐨勯偦闆嗭紝璁頒綔N(S)銆?br> 鏈浼樺尮閰嶏細瀵逛簬涓涓姞鏉冧簩閮ㄥ浘錛屼竴涓潈鏈澶х殑鍖歸厤鍙綔鏈浼樺尮閰嶃?br> 鍙瀹氭爣錛氭槧灝刲錛歏(G)→R錛屾弧瓚沖G鐨勬瘡鏉¤竟e={u, v}錛屽潎鏈塴(u)+l(v)≥w(u, v)錛屽叾涓瓀(u, v)琛ㄧず杈筫鐨勬潈錛屽垯縐發涓篏鐨勫彲琛岄《鏍囥備護El={(u, v) | {u, v}∈E(G)錛宭(u)+l(v)=w(u, v)}錛孏l涓轟互El涓鴻竟闆嗙殑G鐨勭敓鎴愬瓙鍥撅紝鍒欑ОGl涓簂絳夊瓙鍥俱?br>浜屻佹渶澶у尮閰嶏紙鍖堢墮鍒╃畻娉曪級
鎻忚堪錛?/strong>
錛?錛塆鏄叿鏈夊垝鍒?V1, V2)鐨勪簩鍒嗗浘錛屼換緇欏垵濮嬪尮閰峂錛?br> 錛?錛夎嫢M楗卞拰V1鍒欑粨鏉燂紱
錛?錛夊惁鍒欙紝鍦╒1涓壘涓M闈為ケ鍜岀偣錛岋紝緗甋={x}錛?T涓虹┖錛?br> 錛?錛夎嫢N(S) = T錛屽垯鍋滄錛屽惁鍒欎換閫変竴鐐箉∈N(S)-T錛?br> 錛?錛夎嫢y涓篗闈為ケ鍜岀偣錛屽垯姹備竴鏉′粠x鍒皔鐨凪鍙騫胯礬P錛岀疆M涓篗寮傛垨P騫惰漿錛?錛夛紱
錛?錛夊惁鍒欙紝鐢變簬y鏄疢鐨勯ケ鍜岀偣錛屾晠M涓湁涓杈箋y, u}錛岀疆S = S∪{u}錛孴 = T∪{y}錛岃漿錛?錛夈?br> 瀹炵幇錛?br>
1 HUNGARY
2 for i : 1 to |V2|
3 do match[i] = 0
4 for each vertex u in V1
5 do for i : 1 to |V2|
6 do visit[i] = false
7 DFS(u)
8 DFS(u)
9 for each vertex v in V2
10 if (u, v) in E(G) and visit[v] is false
11 then visit[v]=true
12 if match[v] is 0 or DFS(match[v]) is true
13 then match[v] = u
14 return true
15 return false
2 for i : 1 to |V2|
3 do match[i] = 0
4 for each vertex u in V1
5 do for i : 1 to |V2|
6 do visit[i] = false
7 DFS(u)
8 DFS(u)
9 for each vertex v in V2
10 if (u, v) in E(G) and visit[v] is false
11 then visit[v]=true
12 if match[v] is 0 or DFS(match[v]) is true
13 then match[v] = u
14 return true
15 return false
璇存槑錛?/strong>絎?琛岀殑DFS(u)榪囩▼錛屽綋瀛樺湪浠巙寮濮嬬殑M鍙騫胯礬錛屽垯榪斿洖true錛屽茍瀹屾垚M鐨勬墿灞曪紝姝ゆ椂|M|鍔犱竴銆傚鏋滆繑鍥瀎alse錛屽垯琛ㄧず涓嶅瓨鍦∕鍙騫胯礬銆?nbsp;
紺轟緥錛?/strong>POJ 1274 瑙ｉ鎶ュ憡銆?/span>
涓夈佹渶浼樺尮閰嶏紙KM綆楁硶錛?br> 鎻忚堪錛?/strong>
錛?錛変粠浠繪剰鍙欏舵爣l寮濮嬶紝紜畾l絳夊瓙鍥綠l錛屽茍涓斿湪Gl涓夊彇鍖歸厤M銆傝嫢M楗卞拰V1錛屽垯M鏄畬緹庡尮閰嶏紝涔熷嵆M鏄渶浼樺尮閰嶏紝綆楁硶緇堟錛?br> 錛?錛夊惁鍒欙紝榪愮敤鍖堢墮鍒╃畻娉曪紝緇堟浜嶴灞炰簬V1錛孴灞炰簬V2涓斾嬌瀵逛簬Gl錛孨(S)=T銆備護al=min{l(x)+l(y)-w(x, y) | x∈S, y∈V2-T}錛屼護l'(u)=l(u)-al濡傛灉u∈S錛沴'(u)=l(u)+al濡傛灉u∈T錛沴'(u)=l(u)錛屽叾瀹冦傜敤l'浠ｆ浛l錛岀敤Gl'浠ｆ浛Gl杞叆錛?錛夈?br> 瀹炵幇錛?/strong>
1 KUHN-MUNKRES(G)
2 for each vertex u in V1
3 do lx[u] = max{w[u][v] | (u, v) in E(G)}
4 for each vertex v in V2
5 do ly[v] = 0
6 for each vertex u in V1
7 do while(true)
8 do for each vertex u in V1
9 do vx[u] = false
10 for each vertex v in V2
11 do vy[v] = false
12 slack[v] = MAX
13 if DFS(u) is true
14 then break
15 d = min{slack[v] | v in V2 and vy[v] is false}
16 for each vertex u in V1
17 do lx[u] = lx[u] - d
18 for each vertex v in V2
19 do ly[v] = ly[v] + d
20 DFS(u)
21 vx[u] = true
22 for each vertex v in V2
23 do if lx[u]+ly[v]==w[u][v] and vy[v] is false
24 then vy[v] = true
25 if match[v] is NIL or DFS(match[v])
26 then match[v] = u
27 return true
28 else if lx[u]+ly[v]>w[u][v]
29 then slack[v] = min{slack[v], lx[u]+ly[v]-w[u][v]}
30 return false
紺轟緥錛?/span>POJ 2195 瑙ｉ鎶ュ憡 2 for each vertex u in V1
3 do lx[u] = max{w[u][v] | (u, v) in E(G)}
4 for each vertex v in V2
5 do ly[v] = 0
6 for each vertex u in V1
7 do while(true)
8 do for each vertex u in V1
9 do vx[u] = false
10 for each vertex v in V2
11 do vy[v] = false
12 slack[v] = MAX
13 if DFS(u) is true
14 then break
15 d = min{slack[v] | v in V2 and vy[v] is false}
16 for each vertex u in V1
17 do lx[u] = lx[u] - d
18 for each vertex v in V2
19 do ly[v] = ly[v] + d
20 DFS(u)
21 vx[u] = true
22 for each vertex v in V2
23 do if lx[u]+ly[v]==w[u][v] and vy[v] is false
24 then vy[v] = true
25 if match[v] is NIL or DFS(match[v])
26 then match[v] = u
27 return true
28 else if lx[u]+ly[v]>w[u][v]
29 then slack[v] = min{slack[v], lx[u]+ly[v]-w[u][v]}
30 return false
]]>