题解 P4001 【[ICPC-Beijing 2006]狼抓兔子】

· · 题解

玄学dinic居然不会被卡

首先讲讲对偶图，首先对于这样一张图

它的对偶图就是(忽略原来的那9个点)

我们可以把这个对偶图理解为插孔？对偶图的某一边边权就是那条边所交叉的原图的边权。比如上图W_{0->17}=W_{1->4}=5

然后我们就可以用对偶图来维护连通性的问题啦！

先来一道水题（不知道哪来的）

请您维护一张n*n(n\leq1000)的网格图(没有边权)，初始所有边都在，就像这样

这是一张 3*3 的网格图

之后有m(m\leq100000)个操作，割去(x_1,y_1)到(x_2,y_2)的边，保证不会割去重复的边

初始整张图是一个联通块，对于每一次操作，如果使联通块的数量变多了，请输出它是第几个操作。

读完题，发现蒟蒻我不会删边，于是就用到对偶图这个东西。

上文我们提到

对偶图的某一边边权就是那条边所交叉的原图的边权

我们不妨把对偶图的边权理解成割掉原图的边的代价（似乎变成最小割=.=了），于是我们通过维护对偶图的连通性，反而可以得出原图的不连通性。

然后维护连通性用并查集就好了，如果findfa(x1,y1)==findfa(x2,x2),那就ans++（因为题目保证了保证不会割去重复边）

好了，知道了这些知识就可以秒了这道题了

把左下 和 右上分开，dijkstra求左下到右上的最短路

维护对偶图的最短路，反而可以得出原图的最小割

对于题目样例

建一个这样的图，跑dij就行了

只是对偶图建图有点恶心

请自己思考一下怎么转对偶图吧……我是解释不清

//本篇代码以(n,m)为原点 (n+1,m+1)为终点
#include<cstdio>
#include<cstring>
#include<ctime>
#include<algorithm>
#include<queue>

#define rg register
#define MAXN (2000+10)

int head[MAXN][MAXN],tot;
struct edge{
    int next,x,y,w;
}h[MAXN*MAXN*2*2];
inline void addedge(int x,int y,int x1,int y1,int w){   //建边
    h[++tot].next = head[x][y];
    head[x][y] = tot;
    h[tot].x = x1, h[tot].y = y1;
    h[tot].w = w;
}

struct node{
    int x,y,w;
    bool operator < (const node b) const{
        return b.w<w;
    }
};
int n,m;
bool vis[MAXN][MAXN];
int dis[MAXN][MAXN];
void dij(int stx,int sty){//最短路
    memset(dis,0x3f,sizeof(dis));
    std::priority_queue<node> q;
    dis[stx][sty] = 0;
    q.push((node){stx , sty , 0});
    while(!q.empty()){
        node now = q.top();
        q.pop();
        int x = now.x,y = now.y;
        //printf("%d %d \n",x,y);
        if(vis[x][y])   continue;
        vis[x][y] = 1;
        for(rg int i = head[x][y] ; i ; i = h[i].next){
            int tox = h[i].x,toy = h[i].y,w = h[i].w;
            //printf("trying %d %d dis = %d \n",tox,toy,dis[tox][toy]);
            if(dis[x][y] + w < dis[tox][toy]){
                dis[tox][toy] = dis[x][y] + w;
                //printf("CHange dis[%d][%d]=%d \n",tox,toy,dis[tox][toy]);
                if(!vis[tox][toy])  q.push((node){tox,toy,dis[tox][toy]});
            }
        }
    }
    return ;
}

int main(){
    scanf("%d%d",&n,&m);
    if(n==1){
        int ans=1<<30;
        for(rg int i = 1 , w;i < m ; ++i){
            scanf("%d",&w);
            if(w < ans) ans = w;
        }
        printf("%d \n",ans);
        return 0;
    }
    if(m == 1){
        int ans=1<<30;
        for(rg int i = 1 , w;i < n ; ++i){
            scanf("%d",&w);
            if(w < ans) ans = w;
        }
        printf("%d \n",ans);
        return 0;
    }
    for(rg int i = 1 ,w; i <= n ; ++i){
        for(rg int j = 1 ; j < m ; ++j){//此后毒瘤建图
            scanf("%d",&w);
            if(i == 1){
                addedge(i,j<<1,n+1,m+1,w);
                addedge(n+1,m+1,i,j<<1,w);
            }
            else if(i == n){
                addedge(i-1,(j<<1)-1,n,m,w);
                addedge(n,m,i-1,(j<<1)-1,w);
            }
            else{
                addedge(i-1,(j<<1)-1,i,j<<1,w);
                addedge(i,j<<1,i-1,(j<<1)-1,w);
            }
        }
    }
    for(rg int i = 1,w ; i < n ; ++i){
        for(rg int j = 1 ; j <= m ;++j){
            scanf("%d",&w);
            if(j == 1){
                addedge(n,m,i,(j<<1)-1,w);
                addedge(i,(j<<1)-1,n,m,w);
            }
            else if(j == m){
                addedge(n+1,m+1,i,(m-1)<<1,w);
                addedge(i,(m-1)<<1,n+1,m+1,w);
            }
            else{
                addedge(i,(j-1)<<1,i,(j-1)<<1|1,w);
                addedge(i,(j-1)<<1|1,i,(j-1)<<1,w);
            }
        }
    }
    for(rg int i = 1,w; i < n ;i++){
        for(rg int j = 1; j < m ; ++j){
            scanf("%d",&w);
            addedge(i,(j<<1)-1,i,j<<1,w);
            addedge(i,j<<1,i,(j<<1)-1,w);
        }
    }
    dij(n,m);
    printf("%d \n",dis[n+1][m+1]);
    return 0;
}