题目不用描述了，很裸，求一个无向图的最小割。
用网络流+枚举这题肯定TLE，学到一个新算法，贴代码，大家可以作为模板
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表示该点已经被删掉
38
39
40
41 // 结点~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; // 源点
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个结点
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点
122
123
124
125 // 合并k点和源点
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