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

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

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

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

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn = 6e6 + ;

 const int inf = INT_MAX;

 struct node {

     int e, w, next;

 }edge[maxn];

 int head[maxn], len;

 int d[maxn];

 void init() {

     memset(head, -, sizeof(head));

     len = ;

 }

 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 = , f = ; char ch = getchar();

     while (ch<'' || ch>'') { if (ch == '-')f = -; ch = getchar(); }

     while (ch >= ''&&ch <= '') { x = x *  + ch - ; ch = getchar(); }

     return x * f;

 }

 bool bfs(int s, int e) {

     queue<int>q;

     memset(d, , sizeof(d));

     d[s] = ;

     q.push(s);

     while (!q.empty()) {

         int x = q.front(); q.pop();

         for (int i = head[x]; i != -; i = edge[i].next) {

             int y = edge[i].e;

             if (edge[i].w && !d[y]) {

                 d[y] = d[x] + ;

                 q.push(y);

             }

         }

     }

     return d[e];

 }

 int dfs(int s, int e, int limit) {

     if (s == e)

         return limit;

     int add, ans = ;

     for (int i = head[s]; i != -; i = edge[i].next) {

         int y = edge[i].e;

         if (d[s] == d[y] -  && edge[i].w && (add = dfs(y, e, min(edge[i].w, limit)))) {

             edge[i].w -= add;

             edge[i ^ ].w += add;

             ans += add;

             limit -= add;

             if (!limit)

                 break;

         }

     }

     if (ans)

         return ans;

     d[s] = -;

     return ;

 }

 int dinic(int s, int e) {

     int ans = , 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 = ; i <= n; i++)

         for (int j = ; j < m; j++) {

             z = read();

             add(m*(i - ) + j, m*(i - ) + j + , z);

             add(m*(i - ) + j + , m*(i - ) + j, z);

         }

     for (int i = ; i < n; i++)

         for (int j = ; j <= m; j++) {

             z = read();

             add(m*(i - ) + j, m*i + j, z);

             add(m*i + j, m*(i - ) + j, z);

         }

     for (int i = ; i < n; i++)

         for (int j = ; j < m; j++) {

             z = read();

             add(m*(i - ) + j, m*i + j + , z);

             add(m*i + j + , m*(i - ) + j, z);

         }

     printf("%d\n", dinic(, n*m));

     //system("pause");

 }