题目链接:
看到大佬们都是对偶图过的, 写了个最大流水过去了 QAQ, 网络流的无向图直接建双向边 (不用建 0 边), 然后跑 dinic, 最基本的 dinic 会被卡, 可以简单优化一下.
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int maxn = 6e6 + 10;
- const int inf = INT_MAX;
- struct node {
- int e, w, next;
- }edge[maxn];
- int head[maxn], len;
- int d[maxn];
- void init() {
- memset(head, -1, sizeof(head));
- len = 0;
- }
- void add(int s, int e, int w) {
- edge[len].e = e;
- edge[len].w = w;
- edge[len].next = head[s];
- head[s] = len++;
- }
- inline int read() {
- int x = 0, f = 1; char ch = getchar();
- while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
- while (ch>= '0'&&ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
- return x * f;
- }
- bool bfs(int s, int e) {
- queue<int>q;
- memset(d, 0, sizeof(d));
- d[s] = 1;
- q.push(s);
- while (!q.empty()) {
- int x = q.front(); q.pop();
- for (int i = head[x]; i != -1; i = edge[i].next) {
- int y = edge[i].e;
- if (edge[i].w && !d[y]) {
- d[y] = d[x] + 1;
- q.push(y);
- }
- }
- }
- return d[e];
- }
- int dfs(int s, int e, int limit) {
- if (s == e)
- return limit;
- int add, ans = 0;
- for (int i = head[s]; i != -1; i = edge[i].next) {
- int y = edge[i].e;
- if (d[s] == d[y] - 1 && edge[i].w && (add = dfs(y, e, min(edge[i].w, limit)))) {
- edge[i].w -= add;
- edge[i ^ 1].w += add;
- ans += add;
- limit -= add;
- if (!limit)
- break;
- }
- }
- if (ans)
- return ans;
- d[s] = -1;
- return 0;
- }
- int dinic(int s, int e) {
- int ans = 0, f;
- while (bfs(s, e)) {
- while (f = dfs(s, e, inf))
- ans += f;
- }
- return ans;
- }
- int main() {
- int n, m, z;
- n = read(), m = read();
- init();
- for (int i = 1; i <= n; i++)
- for (int j = 1; j < m; j++) {
- z = read();
- add(m*(i - 1) + j, m*(i - 1) + j + 1, z);
- add(m*(i - 1) + j + 1, m*(i - 1) + j, z);
- }
- for (int i = 1; i < n; i++)
- for (int j = 1; j <= m; j++) {
- z = read();
- add(m*(i - 1) + j, m*i + j, z);
- add(m*i + j, m*(i - 1) + j, z);
- }
- for (int i = 1; i < n; i++)
- for (int j = 1; j < m; j++) {
- z = read();
- add(m*(i - 1) + j, m*i + j + 1, z);
- add(m*i + j + 1, m*(i - 1) + j, z);
- }
- printf("%d\n", dinic(1, n*m));
- //system("pause");
- }
[Bzoj1001][BeiJing2006] 狼抓兔子
来源: http://www.bubuko.com/infodetail-3110123.html