_WA自动机的blog

过期高中生。

[BZOJ1001][BeiJing2006]狼抓兔子

发表于 更新于 分类于 ， 阅读次数： Valine：

网格图求最小割？据说这题正解是平面图最小割转对偶图最短路。但是不知为啥数据太水最大流就可以直接过了.. 很久以前的代码了，将就着看吧（虽然这种水题也没人会去看题解... 也许我以后会更一篇正解的题解吧（flag

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
92
93
94
95
96
97
98
99
100
101
102
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
const int inf=1e9;
const int maxm=1e6+5000;
int n,m,maxflow,deep[maxm*6];//deep深度 
struct edge{
    int next,to,dis;
}e[maxm*6];
int tot=-1,head[maxm*6],cur[maxm*6];//cur用于复制head 
 
void add(int x,int y,int z)
{
    e[++tot].to=y;
    e[tot].dis=z;
    e[tot].next=head[x];
    head[x]=tot;
}
 
inline bool bfs(int s,int t)
{
    memset(deep,0x3f,sizeof(deep));
    deep[s]=0;
    memcpy(cur,head,sizeof(head));
    queue<int>q;
    q.push(s);
    while(q.size())
    {
        int x=q.front();q.pop();
        for(int i=head[x];~i;i=e[i].next)
        {
            int y=e[i].to;
            if(deep[y]<=inf||e[i].dis<=0)continue;
            deep[y]=deep[x]+1;
            q.push(y);
        }
    }
    return deep[t]<inf;
}
 
int dfs(int now,int t,int limit)
{
    if(!limit||now==t)return limit;
    int f=0,flow=0;
    for(int i=cur[now];~i;i=e[i].next)
    {
        cur[now]=i;
        int y=e[i].to;
        if(deep[y]==deep[now]+1&&(f=dfs(y,t,min(e[i].dis,limit))))
        {
            limit-=f;
            flow+=f;
            e[i].dis-=f;
            e[i^1].dis+=f;
            if(!limit)break;
        }
    }
    return flow;
}
void Dinic(int s,int t)
{
    while(bfs(s,t))
        maxflow+=dfs(s,t,inf);
}
 
inline int id(int x,int y)
{
    return (x-1)*m+y;
}
 
int main()
{
    memset(head,-1,sizeof(head));
    int w;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)//横向道路
        for(int j=1;j<m;j++)
        {
            scanf("%d",&w);
            add(id(i,j),id(i,j+1),w);
            add(id(i,j+1),id(i,j),w);
        }
    for(int i=1;i<n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&w);
            add(id(i,j),id(i+1,j),w);
            add(id(i+1,j),id(i,j),w);
        }
    for(int i=1;i<n;i++)
        for(int j=1;j<m;j++)
        {
            scanf("%d",&w);
            add(id(i,j),id(i+1,j+1),w);
            add(id(i+1,j+1),id(i,j),w);
        }
    Dinic(id(1,1),id(n,m));
    cout<<maxflow;
}