題目不用描述了，很裸，求一個(gè)無向圖的最小割。
用網(wǎng)絡(luò)流+枚舉這題肯定TLE，學(xué)到一個(gè)新算法，貼代碼，大家可以作為模板
1 #include <cmath>
2
3 #include <cstdio>
4
5 #include <memory.h>
6
7 #include <algorithm>
8
9 #include <iomanip>
10
11 #include <iostream>
12
13 #include <vector>
14
15 #include <string>
16
17 #include <queue>
18
19
20
21 using namespace std;
22
23
24
25 const int N = 500 + 3;
26
27
28
29 int n, m;
30
31 int mat[N][N];
32
33 int dist[N];
34
35 int visited[N];
36
37 int del[N]; // true表示該點(diǎn)已經(jīng)被刪掉
38
39
40
41 // 結(jié)點(diǎn)~n
42
43 int Stoer_Wagner()
44
45 {
46
47 int minCut = INT_MAX; // 無向圖最小割
48
49 int tmp;
50
51 int i, t, j, k, pre;
52
53 int s = 1; // 源點(diǎn)
54
55 memset(del, 0, sizeof(del));
56
57
58
59 for (t = 1; t < n; t++) // n - 1次Maximum Adjacency Search
60
61 {
62
63 for (i = 1; i <= n; i++)
64
65 if (!del[i])
66
67 dist[i] = mat[s][i];
68
69
70
71 memset(visited, 0, sizeof(visited));
72
73 visited[s] = 1;
74
75 k = s;
76
77 for (i = 1; i <= n - t; i++) // 每次剩下n - t + 1個(gè)結(jié)點(diǎn)
78
79 {
80
81 tmp = -1e9;
82
83 pre = k;
84
85 k = 0;
86
87 for (j = 1; j <= n; j++)
88
89 {
90
91 if (!del[j] && !visited[j] && dist[j] > tmp)
92
93 {
94
95 k = j;
96
97 tmp = dist[j];
98
99 }
100
101 }
102
103 if (!k) return 0; // 不連通
104
105
106
107 visited[k] = 1;
108
109 for (j = 1; j <= n; j++)
110
111 if (!del[j] && !visited[j])
112
113 dist[j] += mat[k][j];
114
115 }
116
117
118
119 minCut = min(minCut, dist[k]);
120
121 del[k] = 1; // 刪除k點(diǎn)
122
123
124
125 // 合并k點(diǎn)和源點(diǎn)
126
127
128
129 for (i = 1; i <= n; i++)
130
131 if (!del[i] && i != pre)
132
133 {
134
135 mat[pre][i] += mat[k][i];
136
137 mat[i][pre] = mat[pre][i];
138
139 }
140
141 }
142
143
144
145 return minCut;
146
147 }
148
149
150
151 int main ()
152
153 {
154
155 int u, v, w, i;
156
157 while (scanf("%d%d", &n, &m) != EOF)
158
159 {
160
161 memset(mat, 0, sizeof(mat));
162
163 while (m--)
164
165 {
166
167 scanf("%d%d%d", &u, &v, &w);
168
169 if (u == v) continue;
170
171 mat[u + 1][v + 1] += w;
172
173 mat[v + 1][u + 1] += w;
174
175 }
176
177 printf("%d\n", Stoer_Wagner());
178
179 }
180
181 }
182
183