bzoj1001--最大流转最短路

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

思路：这应该算是经典的最大流求最小割吧。不过题目中n,m<=1000，用最大流会TLE，所以要利用平面图的一些性质。

这里讲一下平面图的对偶图性质。

在平面图中，所有边将图分成了n个平面。我们将平面标号，对于原图中的每条边，在与之相邻的两个平面间连一条边，最后得到的图就是原图的对偶图。

对偶图有如下性质：

1、对偶图的边数与原图相等。

2、对偶图中的每个环对应原图中的割。

于是可以在原图中的s和t间再连一条边，得到对偶图，用spfa求一次最短路就是答案。

具体可以参考http://wenku.baidu.com/link?url=87F10nBWauMdSF-PaKHoG-3fZj0jFE63P6pHSeX6ZiguQqXOQxm41iLWW5IdZCp2MWFQ8JghamfeI68PtLqEv_JSWapGp5z415gNoYb031u

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<vector>

#include<queue>

using namespace std;

#define INF 1000000000

struct edge{

    int p,to;

    edge(int p=,int to=):p(p),to(to){};

};

vector<edge>g[];

queue<int>q;

int i,j,k,n,m,s,t,x,y,d[];

void spfa(){

    for(int i=;i<=t;i++)d[i]=INF;

    q.push();

    while(!q.empty()){

        int x=q.front();q.pop();

        for(int i=;i<g[x].size();i++){

            edge e=g[x][i];

            if(d[x]+e.p<d[e.to]){

                d[e.to]=d[x]+e.p;

                q.push(e.to);

            }

        }

    }

}

int main()

{

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

    if(n==){

        int minn=INF;

        for(i=;i<m;i++){

            scanf("%d",&x);

            minn=min(minn,x);

        }

        printf("%d\n",minn);

        return ;

    }else if(m==){

        int minn=INF;

        for(i=;i<n;i++){

            scanf("%d",&x);

            minn=min(minn,x);

        }

        printf("%d\n",minn);

        return ;

    }

    t=(n-)*(m-)*+;

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

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

        scanf("%d",&k);

        x=(i-)*(m-)*+j*;

        y=(i-)*(m-)*+j*+;

        if(i==)x=;else if(i==n)y=t;

        g[x].push_back(edge(k,y));

        g[y].push_back(edge(k,x));

    }

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

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

        scanf("%d",&k);

        x=(i-)*(m-)*+j*-;

        y=x+;

        if(j==)x=t;else if(j==m)y=;

        g[x].push_back(edge(k,y));

        g[y].push_back(edge(k,x));

    }

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

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

        scanf("%d",&k);

        x=(i-)*(m-)*+j*;

        y=x+;

        g[x].push_back(edge(k,y));

        g[y].push_back(edge(k,x));

    }

    spfa();

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

    return ;

}

巴特西

bzoj1001--最大流转最短路

最新文章

热门文章