P4001

发表于 更新于 分类于
[ICPC-Beijing 2006] 狼抓兔子

[ICPC-Beijing 2006] 狼抓兔子

题目让我们求整张图的最小割。

但我们不需要用最大流最小割定理，因为数据范围不允许。

我们把网格中的每个格子看成一个点，左下方的一片区域和右上方的一片区域分别看成起点和终点。

然后相邻区域之间连边，割掉的那条边就是这两个点之间的边的权值。

这样我们重新建立起一张图，在这里跑起点到终点的最短路就是最小割。

这种建图同样可以推广到所有平面图的情况。

时间复杂度 $O(nm\log nm)$。

连边实际上就是稍微想想啥的。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;

const ll N=3e6;

ll n,m,e1,e2,tot;
ll ver[N*2+5],nxt[N*2+5],wt[N*2+5],head[N+5],f[N+5];
bool vis[N+5];

struct node{
  ll d,v;
  inline bool operator>(const node& rhs) const {return v>rhs.v;}
}t;

priority_queue<node,vector<node>,greater<node> > q;

inline void Dij(ll x) {
  memset(f,0x3f,sizeof(f));
  f[x]=0;t.d=x;t.v=f[x];q.push(t);
  while(!q.empty()) {
    ll h=q.top().d;q.pop();
    if(vis[h]) continue;vis[h]=1;
    for(ll i=head[h];i;i=nxt[i]) {
      if(f[ver[i]]>f[h]+wt[i]) {
        f[ver[i]]=f[h]+wt[i];
        t.d=ver[i];t.v=f[ver[i]];q.push(t);
      }
    }
  }
}

inline void Addedge(ll u,ll v,ll w) {
  ver[++tot]=v;wt[tot]=w;nxt[tot]=head[u];head[u]=tot;
}

inline ll read() {
  ll ret=0,f=1;char ch=getchar();
  while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
  while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
  return ret*f;
}

inline void write(ll x) {
  static char buf[22];static ll len=-1;
  if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
  else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
  while(len>=0) putchar(buf[len--]);
}

int main() {

  n=read();m=read();e1=2*(n-1)*(m-1)+1;e2=2*(n-1)*(m-1)+2;

  for(ll i=1;i<=n;i++) {
    for(ll j=1;j<m;j++) {
      ll w,u,v;w=read();
      u=2*(i-2)*(m-1)+m-1+j;v=2*(i-1)*(m-1)+j;
      if(i==1) u=e1;
      else if(i==n) v=e2;
      Addedge(u,v,w);Addedge(v,u,w);
    }
  }

  for(ll i=1;i<n;i++) {
    for(ll j=1;j<=m;j++) {
      ll w,u,v;w=read();
      u=2*(i-1)*(m-1)+m-1+j;v=2*(i-1)*(m-1)+j-1;
      if(j==1) v=e2;
      else if(j==m) u=e1;
      Addedge(u,v,w);Addedge(v,u,w);
    }
  }

  for(ll i=1;i<n;i++) {
    for(ll j=1;j<m;j++) {
      ll w,u,v;w=read();
      u=2*(i-1)*(m-1)+j;v=2*(i-1)*(m-1)+j+m-1;
      Addedge(u,v,w);Addedge(v,u,w);
    }
  }

  Dij(e1);

  write(f[e2]);

  return 0;
}