当前位置：首页 > news >正文

BZOJ 1001 狼抓兔子（网络流最小割/平面图的对偶图的最短路）

news 来源：原创 2024/5/3 5:25:31

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

算法讨论：

1、可以用最大流做，最大流等于最小割。

2、可以把这个图转化其对偶图，然后在对偶图上跑最短路即可。

一个平面图的最小割等价于其对偶图从S到T的最短路。并不是所有的图都有对偶图，平面图也有一定的要求，自己可以百度一下。

代码（用BZOJ的数据测过了，但是在BZOJ上过不去。爆WA，并不知道是为什么，里面有个特判，并不知道有没有用处。）

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <algorithm>
  5 #include <cstdio>
  6 
  7 using namespace std;
  8 
  9 const int N = 2000000 + 5;
 10 const int inf = 0x3f3f3f3f;
 11 
 12 int n, cnt, m;
 13 int head[N], que[N], dis[N];
 14 bool vis[N];
 15 
 16 struct Edge {
 17   int from, to, dis, next;
 18 }edges[N * 4];
 19 
 20 void add(int u, int v, int dis) {
 21   ++ cnt;
 22   edges[cnt].from = u; edges[cnt].to = v;
 23   edges[cnt].dis = dis; edges[cnt].next = head[u];
 24   head[u] = cnt;
 25   ++ cnt;
 26   edges[cnt].from = v; edges[cnt].to = u;
 27   edges[cnt].dis = dis; edges[cnt].next = head[v];
 28   head[v] = cnt;
 29 }
 30 
 31 void spfa(int s, int t) {
 32   int h = 1, tail = 1;
 33   for(int i = s; i <= t; ++ i) {
 34     dis[i] = inf;
 35     vis[i] = false;
 36   }
 37   vis[s] = true; dis[s] = 0;
 38   que[h] = s;
 39   while(h <= tail) {
 40     int x = que[h];
 41     vis[x] = false;
 42     for(int i = head[x]; i; i = edges[i].next) {
 43       int v = edges[i].to;
 44       if(dis[v] > dis[x] + edges[i].dis) {
 45         dis[v] = dis[x] + edges[i].dis;
 46         if(!vis[v]) {
 47           que[++ tail] = v;
 48           vis[v] = true;
 49         }
 50       }
 51     }
 52     ++ h;
 53   }
 54   printf("%d\n", dis[t]);
 55 }
 56 
 57 #define stone
 58 
 59 int main() {
 60 #ifndef stone
 61 
 62   freopen("bjrabbit.in", "r", stdin);
 63   freopen("bjrabbit.out", "w", stdout);
 64 
 65 #endif
 66   
 67   int tmp, s, t, x, mn = 0x3f3f3f3f;
 68   scanf("%d%d", &n, &m);
 69   s = 0; t = (n - 1) * (m - 1) * 2 + 1;
 70   tmp = (m - 1) * 2;
 71   for(int i = 1; i <= n; ++ i) {
 72     for(int j = 1; j < m; ++ j) {
 73       scanf("%d", &x);
 74       mn = min(x, mn);
 75       if(i == 1) {
 76         add(j * 2 + tmp * (i - 1), t, x);
 77       }
 78       else if(i == n) {
 79         add(s, j * 2 + tmp * (i - 2) - 1, x);
 80       }
 81       else {
 82         add(j * 2 + tmp * (i - 1), j * 2 + tmp * (i - 2) - 1, x);
 83       }
 84     }
 85   }
 86   for(int i = 1; i < n; ++ i) {
 87     for(int j = 1; j <= m; ++ j) {
 88       scanf("%d", &x);
 89       mn = min(x, mn);
 90       if(j == 1) {
 91         add(s, tmp * (i - 1) + 1, x);
 92       }
 93       else if(j == m) {
 94         add(tmp * i, t, x);
 95       }
 96       else {
 97         add(tmp * (i - 1) + 2 * (j - 1), tmp * (i - 1) + 2 * (j - 1) + 1, x);
 98       }
 99     }
100   }
101   for(int i = 1; i < n; ++ i) {
102     for(int j = 1; j < m; ++ j) {
103       scanf("%d", &x);
104       mn = min(mn, x);
105       add(tmp * (i - 1) + j * 2, tmp * (i - 1) + j * 2 - 1, x);
106     }
107   }
108   if(n == 1 || m == 1) printf("%d\n", mn);
109   else spfa(s, t);
110 
111 #ifndef stone
112 
113   fclose(stdin); fclose(stdout);
114 
115 #endif
116   
117   return 0;
118 }