一眼看就是最小割板子题，建图也很直观，注意每一条边建双向边其实不用建4条边，只要反向边的容量和正边相同就行。然后直接跑最大流板子就行。不过此题拿vector存图会MLE……而拿链前存图就能卡过去……场面一度十分尴尬。
这里发一个vector80分代码，各位改成链前就能AC了……
1 #include<cstdio>
2 #include<iostream>
3 #include<cmath>
4 #include<algorithm>
5 #include<cstring>
6 #include<cstdlib>
7 #include<queue>
8 #include<stack>
9 #include<vector>
10 #include<cctype>
11 using namespace std;
12 #define enter puts("")
13 #define space putchar(' ')
14 #define Mem(a) memset(a, 0, sizeof(a))
15 #define rg register
16 typedef long long ll;
17 typedef double db;
18 const int INF = 0x3f3f3f3f;
19 const db eps = 1e-8;
20 const int maxn = 1e6 + 5;
21 inline ll read()
22 {
23 ll ans = 0;
24 char ch = getchar(), last = ' ';
25 while(!isdigit(ch)) {last = ch; ch = getchar();}
26 while(isdigit(ch))
27 {
28 ans = ans * 10 + ch - '0'; ch = getchar();
29 }
30 if(last == '-') ans = -ans;
31 return ans;
32 }
33 inline void write(ll x)
34 {
35 if(x < 0) putchar('-'), x = -x;
36 if(x >= 10) write(x / 10);
37 putchar(x % 10 + '0');
38 }
39
40 int n, m;
41
42 struct Edge
43 {
44 int from, to, cap, flow;
45 };
46 vector<Edge> edges;
47 vector<int> G[maxn];
48 void addedge(int from, int to, int w)
49 {
50 edges.push_back((Edge){from, to, w, 0});
51 edges.push_back((Edge){to, from, w, 0});
52 int sz = edges.size();
53 G[from].push_back(sz - 2);
54 G[to].push_back(sz - 1);
55 }
56
57 int dis[maxn];
58 bool vis[maxn];
59 bool bfs()
60 {
61 for(rg int i = 1; i <= n * m; ++i) vis[i] = 0;
62 dis[1] = 0; vis[1] = 1;
63 queue<int> q; q.push(1);
64 while(!q.empty())
65 {
66 int now = q.front(); q.pop();
67 for(rg int i = 0; i < (int)G[now].size(); ++i)
68 {
69 Edge& e = edges[G[now][i]];
70 if(!vis[e.to] && e.cap > e.flow)
71 {
72 vis[e.to] = 1;
73 dis[e.to] = dis[now] + 1;
74 q.push(e.to);
75 }
76 }
77 }
78 return vis[n * m];
79 }
80 int cur[maxn];
81 int dfs(const int& now, int a)
82 {
83 if(now == n * m || !a) return a;
84 int flow = 0, f;
85 for(int& i = cur[now]; i < (int)G[now].size(); ++i)
86 {
87 Edge& e = edges[G[now][i]];
88 if(dis[e.to] == dis[now] + 1 && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0)
89 {
90 e.flow += f;
91 edges[G[now][i] ^ 1].flow -= f;
92 flow += f; a -= f;
93 if(!a) break;
94 }
95 }
96 return flow;
97 }
98
99 int maxflow()
100 {
101 int flow = 0;
102 while(bfs())
103 {
104 for(rg int i = 1; i <= n * m; ++i) cur[i] = 0;
105 flow += dfs(1, INF);
106 }
107 return flow;
108 }
109
110 int main()
111 {
112 n = read(); m = read();
113 for(rg int i = 1; i <= n; ++i)
114 for(rg int j = 1; j < m; ++j)
115 {
116 int x = read(), from = (i - 1) * m + j, to = (i - 1) * m + j + 1;
117 addedge(from, to, x);
118 }
119 for(rg int i = 1; i < n; ++i)
120 for(rg int j = 1; j <= m; ++j)
121 {
122 int x = read(), from = (i - 1) * m + j, to = i * m + j;
123 addedge(from, to, x);
124 }
125 for(rg int i = 1; i < n; ++i)
126 for(rg int j = 1; j < m; ++j)
127 {
128 int x = read(), from = (i - 1) * m + j, to = i * m + j + 1;
129 addedge(from, to, x);
130 }
131 write(maxflow()); enter;
132 return 0;
133 }
View Code
然后此题据说也可以用对偶图的知识解决。