[Bzoj1001][BeiJing2006]狼抓兔子(网络流/对偶图)

 

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1001

看到大佬们都是对偶图过的，写了个最大流水过去了QAQ，网络流的无向图直接建双向边(不用建0边)，然后跑dinic，最基本的dinic会被卡，可以简单优化一下。

有空学了对偶图在补，(个_个)

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 6e6 + 10;
 5 const int inf = INT_MAX;
 6 struct node {
 7     int e, w, next;
 8 }edge[maxn];
 9 int head[maxn], len;
10 int d[maxn];
11 void init() {
12     memset(head, -1, sizeof(head));
13     len = 0;
14 }
15 void add(int s, int e, int w) {
16     edge[len].e = e;
17     edge[len].w = w;
18     edge[len].next = head[s];
19     head[s] = len++;
20 }
21 inline int read() {
22     int x = 0, f = 1; char ch = getchar();
23     while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
24     while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
25     return x * f;
26 }
27 bool bfs(int s, int e) {
28     queue<int>q;
29     memset(d, 0, sizeof(d));
30     d[s] = 1;
31     q.push(s);
32     while (!q.empty()) {
33         int x = q.front(); q.pop();
34         for (int i = head[x]; i != -1; i = edge[i].next) {
35             int y = edge[i].e;
36             if (edge[i].w && !d[y]) {
37                 d[y] = d[x] + 1;
38                 q.push(y);
39             }
40         }
41     }
42     return d[e];
43 }
44 int dfs(int s, int e, int limit) {
45     if (s == e)
46         return limit;
47     int add, ans = 0;
48     for (int i = head[s]; i != -1; i = edge[i].next) {
49         int y = edge[i].e;
50         if (d[s] == d[y] - 1 && edge[i].w && (add = dfs(y, e, min(edge[i].w, limit)))) {
51             edge[i].w -= add;
52             edge[i ^ 1].w += add;
53             ans += add;
54             limit -= add;
55             if (!limit)
56                 break;
57         }
58     }
59     if (ans)
60         return ans;
61     d[s] = -1;
62     return 0;
63 }
64 int dinic(int s, int e) {
65     int ans = 0, f;
66     while (bfs(s, e)) {
67         while (f = dfs(s, e, inf))
68             ans += f;
69     }
70     return ans;
71 }
72 int main() {
73     int n, m, z;
74     n = read(), m = read();
75     init();
76     for (int i = 1; i <= n; i++)
77         for (int j = 1; j < m; j++) {
78             z = read();
79             add(m*(i - 1) + j, m*(i - 1) + j + 1, z);
80             add(m*(i - 1) + j + 1, m*(i - 1) + j, z);
81         }
82     for (int i = 1; i < n; i++)
83         for (int j = 1; j <= m; j++) {
84             z = read();
85             add(m*(i - 1) + j, m*i + j, z);
86             add(m*i + j, m*(i - 1) + j, z);
87         }
88     for (int i = 1; i < n; i++)
89         for (int j = 1; j < m; j++) {
90             z = read();
91             add(m*(i - 1) + j, m*i + j + 1, z);
92             add(m*i + j + 1, m*(i - 1) + j, z);
93         }
94     printf("%d\n", dinic(1, n*m));
95     //system("pause");
96 }

 

 

原文链接:https://www.cnblogs.com/sainsist/p/11115356.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有