bzoj1001狼抓兔子 对偶图优化

链接

https://www.lydsy.com/JudgeOnline/problem.php?id=1001

思路

菜鸡总是要填坑的！

很明显让你求网格图的最小割

不过1000*1000明显不能跑dinic(虽然可以水过)

我们可以用对偶图来优化辣。

对偶图是啥？可以用最短路来求最小割的东西，论文写的特清楚。

代码

#include <iostream>

#include <cstring>

#include <queue>

#include <cstdio>

#include <algorithm>

using namespace std;

const int N=2e6+7;

int read() {

    int x=0,f=1;char s=getchar();

    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;

    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';

    return x*f;

}

int n,m,S,T;

struct edge {

    int v,nxt,q;

}e[N*5];

int head[N*5],tot;

void add(int u,int v,int q) {

//	cout<<u<<" "<<v<<" "<<q<<"\n";

    e[++tot].v=v;

    e[tot].q=q;

    e[tot].nxt=head[u];

    head[u]=tot;

}

struct node {

    int x,y;

    bool operator < (const node &b) const {

        return x>b.x;

    }

};

priority_queue<node> q;

int dis[N];

void dij() {

    memset(dis,0x3f,sizeof(dis));

    q.push((node){0,S});

    dis[S]=0;

    while(!q.empty()) {

        node u=q.top();

        q.pop();

        if(u.x!=dis[u.y]) continue;

//		cout<<head[S]<<" "<<<<"\n";

        for(int i=head[u.y];i;i=e[i].nxt) {

            int v=e[i].v;

//			cout<<u.y<<" -> "<<v<<" "<<e[i].q<<"\n";

            if(dis[v]>dis[u.y]+e[i].q) {

                dis[v]=dis[u.y]+e[i].q;

                q.push((node){dis[v],v});

            }

        }

    }

}

int main() {

//	freopen("a.in","r",stdin);

    n=read(),m=read();

    S=n*m*2+1,T=n*m*2+2;

//	cout<<S<<" "<<T<<"\n";

    for(int i=1,TX,TY,x;i<=n;++i) {

        for(int j=1;j<m;++j) {

            x=read();

            TX=(i-1)*(m-1)*2+j,TY=TX-(m-1);

            if(i==1) TY=S;

            if(i==n) TX=T;

            add(TX,TY,x);

            add(TY,TX,x);

        }

    }

    for(int i=1,TX,TY,x;i<n;++i) {

        for(int j=1;j<=m;++j) {

            x=read();

            TX=(i-1)*(m-1)*2+j+(m-1),TY=TX-(m-1)-1;

            if(j==1) TY=T;

            if(j==m) TX=S;

            add(TX,TY,x);

            add(TY,TX,x);

        }

    }

    for(int i=1,TX,TY,x;i<n;++i) {

        for(int j=1;j<m;++j) {

            x=read();

            TX=(i-1)*(m-1)*2+j,TY=TX+(m-1);

            add(TX,TY,x);

            add(TY,TX,x);

        }

    }

    dij();

    printf("%d\n",dis[T]);

    return 0;

}