【题意】：给出n个人，f[i][j]表示他们的友好程度，现在要把这n个人分成两组，使得所有人的开心程度之和最大，既∑∑(-1)
1-s[i][j]f[i][j]最大化。其中，s[i][j]表示i和j是否同一组。
【题解】：先假设所有人都在同一组，sum = ∑f[i][j]，然后我们需要改变某些人的关系使得n个人分成两组且代价最小，这样问题就转为求一个无向图的全局最小割。
最后答案为sum - 4 * mincut。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define mp make_pair
15 #define fi first
16 #define se second
17 #define lc(x) (x << 1)
18 #define rc(x) (x << 1 | 1)
19 #define lowbit(x) (x & (-x))
20 #define ll long long
21
22 #define maxn 100
23 const int inf = 1 << 27;
24 int maz[maxn][maxn];
25 int n, m;
26
27 int StoerWagner(int n) {//n 为点数
28 int v[maxn], dist[maxn];
29 bool visit[maxn];
30 int cut = inf;
31 for(int i = 0; i < n; i++) v[i] = i;
32 while(n > 1) {
33 int k = 1, pre = 0;
34 for(int i = 1; i < n; i++) {
35 dist[v[i]] = maz[v[0]][v[i]];
36 if(dist[v[i]] > dist[v[k]]) k = i;
37 }
38 memset(visit, false, sizeof(visit));
39 visit[v[0]] = true;
40 for(int i = 1; i < n; i++) {
41 if(i == n - 1) {
42 cut = min(cut, dist[v[k]]);
43 for(int j = 0; j < n; j++) {
44 maz[v[pre]][v[j]] += maz[v[j]][v[k]];
45 maz[v[j]][v[pre]] += maz[v[j]][v[k]];
46 }
47 v[k] = v[--n];
48 }
49 visit[v[k]] = true;
50 pre = k, k = -1;
51 for(int j = 1; j < n; j++) {
52 if(!visit[v[j]]) {
53 dist[v[j]] += maz[v[pre]][v[j]];
54 if(k == -1 || dist[v[k]] < dist[v[j]])
55 k = j;
56 }
57 }
58 }
59 }
60 return cut;
61 }
62
63 int main() {
64 int T;
65 while(scanf("%d", &T), T) {
66 while(T--) {
67 scanf("%d%d", &n, &m);
68 memset(maz, 0, sizeof(maz));
69 int sum = 0;
70 for(int i = 0; i < n; i++)
71 for(int j = 0; j < n; j++) {
72 scanf("%d", &maz[i][j]);
73 sum += maz[i][j];
74 }
75 int ans = sum - 4 * StoerWagner(n);
76 cout << ans << endl;
77 }
78 }
79 return 0;
80 }
81