Eternity

Until The End

P4001 [ICPC-Beijing 2006] 狼抓兔子 & UVA1376 Animal Run

发表于 分类于
本文字数： 4.4k 阅读时长 ≈ 4 分钟

网络流建原始对偶图解决最小割问题。

很显然地，这道题就是求一个图的最小割，直接 $\text{Dinic}$ 解决就好了，但是，会发现一个致命的问题——$n,m\leq 1000$ ，而对于这张图而言，点和边的数量可以达到 $1e6$ 级别，网络流多半是跑不过的，这时候，就要请出对偶图的概念了。

对于一张有最小割的网络（当然，其它图可能也有），都存在其对偶图。

存在对偶图的条件：原图中没有任何两条边相交（所以网格图一定存在对偶图）。

本道题的样例的对偶图长这样（有些丑）：

example

就会发现，所谓的对偶图，就是对每一个封闭的区域建立一个结点（之外视作同一区域），然后点于点之间连一条边，就会发现，原来的每一条边都被“割”了一次，而所求出的使原来 $start,end$ 隔离的最小代价，就是使现在的 $S,T$ 连通的最小代价，而这个东西，就是最短路。那么，我们就可以用 $\text{Dijkstra}$ 在 $\mathcal O(n\log m)$ 时间内解决网格图最小割问题了（所以说这也是 $\text{CSP-S 2021}$ 的 $\text{T4}$ 交通规划的正解）。

有请出双倍经验。洛谷上的那道题数据较水，似乎网络流可过，$\text{UVa}$ 多组数据，只能拿对偶图跑。

先贴一个网络流的代码，注意是双向边：

AC Code 
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
const int MAXV=1e6+10,MAXE=4e6+10,MAXN=1e3+10;
const int INF=0x3f3f3f3f;
int N,M,S,T;
struct Net
{
    int next,to,val;
}Edge[MAXE<<1];
int Head[MAXV],Cur[MAXV],Total=1;
inline void addEdge(int u,int v,int w)
{
    Edge[++Total]=(Net){Head[u],v,w};Head[u]=Total;
    Edge[++Total]=(Net){Head[v],u,0};Head[v]=Total;
}
int Fl[MAXV];
inline bool Bfs()
{
    memset(Fl,-1,sizeof(Fl));
    std::queue<int>Q;
    Q.push(S),Fl[S]=0,Cur[S]=Head[S];
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        for(int e=Head[u],v;e;e=Edge[e].next)
        {
            v=Edge[e].to;
            if(Fl[v]==-1&&Edge[e].val)
            {
                Fl[v]=Fl[u]+1,Cur[v]=Head[v];
                if(v==T) return 1;
                Q.push(v);
            }
        }
    }
    return 0;
}
int Dfs(int x,int inf)
{
    if(x==T) return inf;
    int flow=0;
    for(int e=Cur[x],v;e&&flow<inf;e=Edge[e].next)
    {
        v=Edge[e].to,Cur[x]=e;
        if(Fl[v]==Fl[x]+1&&Edge[e].val)
        {
            int k=Dfs(v,std::min(inf-flow,Edge[e].val));
            if(!k) Fl[v]=-1;
            Edge[e].val-=k,Edge[e^1].val+=k,flow+=k;
        }
    }
    return flow;
}
inline int Dinic()
{
    int r=0,flow;
    while(Bfs()) while(flow=Dfs(S,INF)) r+=flow;
    return r;
}
inline int getId(int x,int y)
{
    return M*(x-1)+y;
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(N,M);
    S=0,T=N*M+1;
    addEdge(S,getId(1,1),INF),addEdge(getId(N,M),T,INF);
    for(int i=1;i<=N;++i)
        for(int j=1,x;j<M;++j)
        {
            read(x);
            addEdge(getId(i,j),getId(i,j+1),x);
            addEdge(getId(i,j+1),getId(i,j),x);
        }
    for(int i=1;i<N;++i)
        for(int j=1,x;j<=M;++j)
        {
            read(x);
            addEdge(getId(i,j),getId(i+1,j),x);
            addEdge(getId(i+1,j),getId(i,j),x);
        }
    for(int i=1;i<N;++i)
        for(int j=1,x;j<M;++j)
        {
            read(x);
            addEdge(getId(i,j),getId(i+1,j+1),x);
            addEdge(getId(i+1,j+1),getId(i,j),x);
        }
    write(Dinic());
    return 0;
}
/*
3 4
5 6 4
4 3 1
7 5 3
5 6 7 8
8 7 6 5
5 5 5
6 6 6
*/

$V=2(n-1)(m-1)+2$

$E=4(n-1)(m-1)+4(n+m)+4$

AC Code 
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
const int MAXV=2e6+10,MAXE=4e6+10,MAXN=1e3+10;
int N,M,S,T;
struct Net
{
    int next,to,val;
}Edge[MAXE<<1];
struct Que
{
    int x,d;
    Que(int x=0,int d=0):x(x),d(d){}
    bool operator<(const Que& x) const
    { return d>x.d; }
};
int Head[MAXV],Total;
inline void addEdge(int u,int v,int w)
{
    Edge[++Total]=(Net){Head[u],v,w};Head[u]=Total;
    Edge[++Total]=(Net){Head[v],u,w};Head[v]=Total;
}
int Dist[MAXV];
bool Vis[MAXV];
inline void Dijkstra()
{
    std::priority_queue<Que>Q;
    memset(Dist,0x3f,sizeof(Dist));
    memset(Vis,0,sizeof(Vis));
    Dist[S]=0;
    Q.push(Que(S,Dist[S]));
    while(!Q.empty())
    {
        int u=Q.top().x;Q.pop();
        Vis[u]=1;
        for(int e=Head[u],v;e;e=Edge[e].next)
        {
            v=Edge[e].to;
            if(Dist[v]>Dist[u]+Edge[e].val)
            {
                Dist[v]=Dist[u]+Edge[e].val;
                if(!Vis[v]) Q.push(Que(v,Dist[v]));
            }
        }
    }
}
int Blk[MAXN][MAXN][2],Idx;
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(N,M);
    S=2*(N-1)*(M-1)+1,T=S+1;
    for(int i=1;i<N;++i)
        for(int j=1;j<M;++j)
            Blk[i][j][0]=++Idx,Blk[i][j][1]=++Idx;
    for(int i=1;i<=N;++i)
        for(int j=1,x;j<M;++j)
        {
            read(x);
            if(i==1) addEdge(Blk[1][j][0],T,x);
            else if(i==N) addEdge(S,Blk[N-1][j][1],x);
            else addEdge(Blk[i-1][j][1],Blk[i][j][0],x);
        }
    for(int i=1;i<N;++i)
        for(int j=1,x;j<=M;++j)
        {
            read(x);
            if(j==1) addEdge(S,Blk[i][1][1],x);
            else if(j==M) addEdge(Blk[i][M-1][0],T,x);
            else addEdge(Blk[i][j][1],Blk[i][j-1][0],x);
        }
    for(int i=1;i<N;++i)
        for(int j=1,x;j<M;++j)
        {
            read(x);
            addEdge(Blk[i][j][0],Blk[i][j][1],x);
        }
    Dijkstra();
    write(Dist[T]);
    return 0;
}
/*
3 4
5 6 4
4 3 1
7 5 3
5 6 7 8
8 7 6 5
5 5 5
6 6 6
*/
相关文章