BZOJ - 1001 狼抓兔子(网络流最小割转对偶图最短路)

Posted on | In ,

思路

题意可得我们要求一个网络流的最小割。但由于dinic时间复杂度是O(EV^2)，显然对于这张图来说边数会达到10^6以上，所以dinic的时间复杂度是不满足我们的要求的。所以我们学习一个O(nlogn)的姿势——网络流最小割转对偶图最短路。对偶图的概念摸这里。通过观察我们能发现对偶图中的环即对应着原图的割，但直接用对偶图环的性质我们并没有什么高效的算法。所以我们在建图过程中稍作修改，我们这样对样例建图：
bzoj1001
我们先在左上角的源点和右下角的汇点连一条线，如上图，然后再建对偶图。这时比较对偶图的性质显然可以知道对偶图中0到1的最短路即为最小割，运用spfa或dijkstra堆优化就能做到O(nlogn)。

代码

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
103
104
105
106
107
108
#include <bits/stdc++.h>
#define ms(a,val) memset(a,val,sizeof(a))
#define ll long long
#define INF 0x7fffffff

using namespace std;

const int MAXN=2000005,MAXM=6000005;
int head[MAXN],nxt[MAXM],to[MAXM],len[MAXM],edgecnt;
void addedge(int u,int v,int w){
    to[edgecnt]=v;
    len[edgecnt]=w;
    nxt[edgecnt]=head[u];
    head[u]=edgecnt++;
}
struct cmp{
    bool operator ()(pair<int,int> p1,pair<int,int> p2){
        return p1.first>p2.first;
    }
};
int dist[MAXN],N;
void dijkstra(int s){
    for(int i=0;i<N;i++)dist[i]=INF;
    dist[s]=0;
    priority_queue<pair<int,int>,vector<pair<int,int> >,cmp> pq;
    pq.push(make_pair(0,s));
    while(!pq.empty()){
        pair<int,int> temp=pq.top();
        pq.pop();
        int now=temp.second,dis=temp.first;
        if(dist[now]<dis)continue;
        for(int i=head[now];~i;i=nxt[i]){
            if(dist[now]+len[i]<dist[to[i]]){
                dist[to[i]]=dist[now]+len[i];
                pq.push(make_pair(dist[to[i]],to[i]));
            }
        }
    }
}

int main() {
    int n,m,cost;
    while(~scanf("%d%d",&n,&m)){
        ms(head,-1);
        edgecnt=0;
        if(n==1||m==1){
            int ans=0;
            if(n>m)m=n;
            for(int z=1;z<m;z++){
                if(z==1)scanf("%d",&ans);
                int t;
                scanf("%d",&t);
                if(t<ans)ans=t;
            }
            printf("%d\n",ans);
        }
        else{
            N=(n-1)*(m-1)*2+2;
            for(int i=0;i<n;i++){
                for(int j=1;j<=m-1;j++){
                    scanf("%d",&cost);
                    if(i==0){
                        //cout<<0<<" "<<2*j<<endl;
                        addedge(0,2*j,cost);
                    }
                    else if(i==n-1){
                        //cout<<2*((m-1)*(i-1)+j)+1<<" "<<1<<endl;
                        addedge(2*((m-1)*(i-1)+j)+1,1,cost);
                    }
                    else{
                        //cout<<2*((m-1)*(i-1)+j)+1<<" "<<2*((m-1)*i+j)<<endl;
                        addedge(2*((m-1)*(i-1)+j)+1,2*((m-1)*i+j),cost);
                        addedge(2*((m-1)*i+j),2*((m-1)*(i-1)+j)+1,cost);
                    }
                }
            }
            for(int j=0;j<n-1;j++){
                for(int i=0;i<m;i++){
                    scanf("%d",&cost);
                    if(i==0){
                        //cout<<2*((m-1)*j+i+1)+1<<" "<<1<<endl;
                        addedge(2*((m-1)*j+i+1)+1,1,cost);
                    }
                    else if(i==m-1){
                        //cout<<0<<" "<<2*((m-1)*j+i)<<endl;
                        addedge(0,2*((m-1)*j+i),cost);
                    }
                    else{
                        //cout<<2*((m-1)*j+i)<<" "<<2*((m-1)*j+i+1)+1<<endl;
                        addedge(2*((m-1)*j+i),2*((m-1)*j+i+1)+1,cost);
                        addedge(2*((m-1)*j+i+1)+1,2*((m-1)*j+i),cost);
                    }
                }
            }
            for(int i=0;i<n-1;i++){
                for(int j=1;j<=m-1;j++){
                    scanf("%d",&cost);
                    //cout<<2*((m-1)*i+j)<<" "<<2*((m-1)*i+j)+1<<endl;
                    addedge(2*((m-1)*i+j),2*((m-1)*i+j)+1,cost);
                    addedge(2*((m-1)*i+j)+1,2*((m-1)*i+j),cost);
                }
            }
            dijkstra(0);
            printf("%d\n",dist[1]);
        }
    }
	return 0;
}