[BeiJing2006]狼抓兔子 dijkstra+平面图最小割

一眼裸的最大流求最小割，然而数据范围过大，跑不下来。

我们可以将平面图转成对偶图，并进行连边。

这样，每条边的长度就对应原图中的割边长度。

起点到终点的最短路即为最小割。

别用SPFA，会死的很惨

Code:

#include<vector>

#include<queue>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<string>

#include<iostream>

#define U(i)  ((i-1)<<1)|1

#define D(i)  (i<<1)

using namespace std;

void SetIO(string a){

	string in=a+".in",out=a+".out";

	freopen(in.c_str(),"r",stdin);

	freopen(out.c_str(),"w",stdout);

}

int s,t,n,m;

const int maxn=6000000+4;

int head[maxn],to[maxn],nex[maxn],val[maxn],edges,idx[1103][1103];

void add_edge(int u,int v,int c){

	nex[++edges]=head[u], head[u]=edges, to[edges]=v, val[edges]=c;

}

void build_row(int i,int j,int k){

	if(i==1)add_edge(s,U(idx[i][j]),k);

	else if(i==n) add_edge(D(idx[i-1][j]),t,k);

	else add_edge(D(idx[i-1][j]),U(idx[i][j]),k),add_edge(U(idx[i][j]),D(idx[i-1][j]),k);

}

void build_col(int i,int j,int k){

	if(j==1)add_edge(D(idx[i][j]),t,k);

	else if(j==m) add_edge(s,U(idx[i][j-1]),k);

	else add_edge(D(idx[i][j]),U(idx[i][j-1]),k),add_edge(U(idx[i][j-1]),D(idx[i][j]),k);

}

void build_cross(int i,int j,int k){

	add_edge(U(idx[i][j]),D(idx[i][j]),k);

	add_edge(D(idx[i][j]),U(idx[i][j]),k);

}

long long d[maxn];

struct cmp{

    bool operator()(int a,int b){

        return d[a]>d[b];

    }

};

priority_queue<long long ,vector<long long>,cmp>Q;

long long  dijkstra()

{

	bool done[maxn];

	memset(done,false,sizeof(done));

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

    d[s]=0;

    Q.push(s);

    while(!Q.empty())

    {

        int u=Q.top();

        Q.pop();

        if(done[u])continue;

        done[u]=1;

        if(u==t) break;

        for(int v=head[u];v;v=nex[v])

            if(d[u]+val[v]<d[to[v]])

            {

                d[to[v]]=d[u]+val[v];

                Q.push(to[v]);

            }

    }

    return d[t];

}

int main(){

	SetIO("input");

	scanf("%d%d",&n,&m);

	s=0,t=((n*m)<<1)+6666;

	int cur=0,cost=0;

	for(int i=1;i<n;++i)

		for(int j=1;j<m;++j) idx[i][j]=++cur;

	for(int i=1;i<=n;++i)

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

			scanf("%d",&cost);

			build_row(i,j,cost);

		}

	for(int i=1;i<n;++i)

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

			scanf("%d",&cost);

			build_col(i,j,cost);

		}

	for(int i=1;i<n;++i)

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

			scanf("%d",&cost);

			build_cross(i,j,cost);

		}

	printf("%lld",dijkstra());

	return 0;

}

　　

---恢复内容结束---