Description
文理分科是一件很纠结的事情！（虽然看到这个题目的人肯定都没有纠
结过）
小P所在的班级要进行文理分科。他的班级可以用一个n*m的矩阵进行
描述，每个格子代表一个同学的座位。每位同学必须从文科和理科中选择
一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式
得到：
1．如果第i行第秒J的同学选择了文科，则他将获得art[i][j]的满意值，如
果选择理科，将得到science[i][j]的满意值。
2．如果第i行第J列的同学选择了文科，并且他相邻（两个格子相邻当且
仅当它们拥有一条相同的边）的同学全部选择了文科，则他会更开
心，所以会增加same_art[i][j]的满意值。
3．如果第i行第j列的同学选择了理科，并且他相邻的同学全部选择了理
科，则增加same_science[i]j[]的满意值。
小P想知道，大家应该如何选择，才能使所有人的满意值之和最大。请
告诉他这个最大值。
Input
第一行为两个正整数：n，m
接下来n术m个整数，表示art[i][j]；
接下来n术m个整数．表示science[i][j]；
接下来n术m个整数，表示same_art[i][j]；
Output
输出为一个整数，表示最大的满意值之和
Sample Input
3 4
13 2 4 13
7 13 8 12
18 17 0 5
8 13 15 4
11 3 8 11
11 18 6 5
1 2 3 4
4 2 3 2
3 1 0 4
3 2 3 2
0 2 2 1
0 2 4 4
13 2 4 13
7 13 8 12
18 17 0 5
8 13 15 4
11 3 8 11
11 18 6 5
1 2 3 4
4 2 3 2
3 1 0 4
3 2 3 2
0 2 2 1
0 2 4 4
Sample Output
152
HINT
样例说明
1表示选择文科，0表示选择理科，方案如下：
1 0 0 1
0 1 0 0
1 0 0 0
N,M<=100,读入数据均<=500
Solution
试机的时候写的。。。贾教流。
对于一个集合选or不选产生的代价/价值可以通过新建附加点来解决。
Code
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <algorithm> 5 6 #define R register 7 #define filename "" 8 9 #define maxn 100010 10 #define maxm 600010 11 #define inf 0x7fffffff 12 #define dmin(_a, _b) ((_a) < (_b) ? (_a) : (_b)) 13 struct Edge { 14 Edge *next, *rev; 15 int to, cap; 16 } *cur[maxn], *last[maxn], e[maxm], *ecnt = e; 17 inline void link(R int a, R int b, R int w) 18 { 19 *++ecnt = (Edge) {last[a], ecnt + 1, b, w}; last[a] = ecnt; 20 *++ecnt = (Edge) {last[b], ecnt - 1, a, 0}; last[b] = ecnt; 21 } 22 const int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1}; 23 int id[110][110], s, t, ans, q[maxn], dep[maxn], tot; 24 inline bool bfs() 25 { 26 R int head = 0, tail = 1; 27 memset(dep, -1, (tot + 1) << 2); 28 dep[q[1] = t] = 0; 29 while (head < tail) 30 { 31 R int now = q[++head]; 32 for (R Edge *iter = last[now]; iter; iter = iter -> next) 33 if (iter -> rev -> cap && dep[iter -> to] == -1) 34 dep[q[++tail] = iter -> to] = dep[now] + 1; 35 } 36 return dep[s] != -1; 37 } 38 int dfs(R int x, R int f) 39 { 40 if (x == t) return f; 41 R int used = 0; 42 for (R Edge* &iter = cur[x]; iter; iter = iter -> next) 43 if (iter -> cap && dep[iter -> to] + 1 == dep[x]) 44 { 45 R int v = dfs(iter -> to, dmin(iter -> cap, f - used)); 46 iter -> cap -= v; 47 iter -> rev -> cap += v; 48 used += v; 49 if (used == f) return f; 50 } 51 return used; 52 } 53 inline void dinic() 54 { 55 while (bfs()) 56 { 57 memcpy(cur, last, (tot + 1) << 2); 58 ans += dfs(s, inf); 59 } 60 } 61 int main() 62 { 63 // freopen(filename".in", "r", stdin); 64 // freopen(filename".out", "w", stdout); 65 R int n, m; scanf("%d%d", &n, &m); 66 R int anss = 0; 67 for (R int i = 1; i <= n; ++i) 68 for (R int j = 1; j <= m; ++j) 69 { 70 id[i][j] = ++tot; R int art; 71 scanf("%d", &art); link(s, tot, art); anss += art; 72 } 73 t = ++tot; 74 for (R int i = 1; i <= n; ++i) 75 for (R int j = 1; j <= m; ++j) 76 { 77 R int sc; scanf("%d", &sc); anss += sc; 78 link(id[i][j], t, sc); 79 } 80 for (R int i = 1; i <= n; ++i) 81 for (R int j = 1; j <= m; ++j) 82 { 83 R int as; scanf("%d", &as); ++tot; anss += as; 84 for (R int k = 0; k < 4; ++k) 85 { 86 R int nx = i + dx[k], ny = j + dy[k]; 87 if (id[nx][ny]) link(tot, id[nx][ny], inf); 88 } 89 link(tot, id[i][j], inf); 90 link(s, tot, as); 91 } 92 for (R int i = 1; i <= n; ++i) 93 for (R int j = 1; j <= m; ++j) 94 { 95 R int ss; scanf("%d", &ss); ++tot; anss += ss; 96 for (R int k = 0; k < 4; ++k) 97 { 98 R int nx = i + dx[k], ny = j + dy[k]; 99 if (id[nx][ny]) link(id[nx][ny], tot, inf); 100 } 101 link(id[i][j], tot, inf); 102 link(tot, t, ss); 103 } 104 dinic(); 105 printf("%d ", anss - ans); 106 return 0; 107 }