UVA 10480 Sabotage (最大流) 最小割边

题意：

编写一个程序，给定一个网络规范和破坏每个连接的成本，确定要切断哪个连接，以便将首都和最大的城市分离到尽可能低的成本。

分割-----------------------------------------

这道题的意思要把一个图分成两部分，要把点1和点2分开。隔断每条边都有一个花费，求最小花费的情况下，应该切断那些边。
这题很明显是最小割，也就是最大流。把1当成源点，2当成汇点。
问题是要求最小割应该隔断那条边。

输入：

输入文件包含几组输入。每一组的描述如下。每个集合的第一行有两个整数，用空格隔开:第一个是网络中的城市数量n，最多为50。第二个是连接的总数，m，最多500。以下m行指定连接。每条线由三部分组成，中间用空格隔开:前两部分是由这两部分连接起来的城市(数字在1 - n范围内)。然后是切断连接的成本(范围为1到40000000的整数)。在这个列表中，每对引用最多只能出现一次。当n和m的值为0时，输入终止。这种情况不应该处理。对于每个输入集，首都是第1个城市，最大的城市是第2个城市。

输出：

对于每个输入集，您应该生成几行输出。每个输入集的输出描述如下:每个输入集的输出应该是城市对(即数字)，它们之间的连接应该被切断(以任何顺序)，每对在一行，数字之间用空格隔开。如果有多个解决方案，任何一个都可以。在每个输入集的输出之后打印空行。

题解：

 1 void addedge(int u, int v, int w)  //建双向边

 2 {  //u为起点，v为终点，w为边上的流量

 3     edge[tot].v = v;

 4     edge[tot].w = w;

 5     edge[tot].next = head[u];

 6     head[u] = tot++;

 7

 8     edge[tot].v = u;

 9     edge[tot].w = w;

10     edge[tot].next = head[v];

11     head[v] = tot++;

12     return;

13 }

我之前就有一个疑问就是，为什么在建有向边的时候还要建一条容量为0的反向边。

其实这就是为了反悔之前的操作，因为我们第一次跑最大流的时候肯定会有好多路都可以跑到终点。但是我们最后要的是最大流，这就要考虑到最优策略，所以我们之前走过的路可能要改变。这个时候建立反向边的作用就体现了

代码：

//本题是可以双向走，那么我们正向也可以反向也可以，所以我们在建反向边的时候就不能给它初始值为0，因为

//他刚开始反向边就可以走

//在最后一次bfs之后，肯定就会出现断层(即，到不了终点)，这个时候因为中间出现了流量为0所以到不了，

//那么这些流量为0就是我们删去的边

#include<stdio.h>

#include<string.h>

#include<iostream>

#include<algorithm>

#include<queue>

using namespace std;

const int maxn=10005;

const int INF=0x3f3f3f3f;

int head[maxn],cnt,st,en,dis[maxn],cur[maxn],xx[maxn],yy[maxn];

struct edge

{

    int v,next,c,flow;

} e[100005];

void add_edge(int x,int y,int z)

{

    e[cnt].v=y;

    e[cnt].c=z;

    e[cnt].flow=0;

    e[cnt].next=head[x];

    head[x]=cnt++;

}

bool bfs()

{

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

    dis[st]=1;

    queue<int>r;

    r.push(st);

    while(!r.empty())

    {

        int x=r.front();

        r.pop();

        for(int i=head[x];i!=-1;i=e[i].next)

        {

            int v=e[i].v;

            if(!dis[v] && e[i].c>e[i].flow)

            {

                dis[v]=dis[x]+1;

                r.push(v);

            }

        }

    }

    return dis[en];

}

int dinic(int s,int limit)

{

    if(s==en || !limit) return limit;

    int ans=0;

    for(int &i=cur[s];i!=-1;i=e[i].next)

    {

        int v=e[i].v,feed;

        if(dis[v]!=dis[s]+1) continue;

        feed=dinic(v,min(limit,e[i].c-e[i].flow));

        if(feed)

        {

            e[i].flow+=feed;

            e[i^1].flow-=feed;

            limit-=feed;

            ans+=feed;

            if(limit==0) break;

        }

    }

    if(!ans) dis[s]=-1;

    return ans;

}

int main()

{

    int s,d,n,m;

    while(~scanf("%d%d",&n,&m) && n+m)

    {

        memset(head,-1,sizeof(head));

        cnt=0;

        st=1;

        en=2;

        int x,y,z;

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

        {

            scanf("%d%d%d",&x,&y,&z);

            xx[i]=x;

            yy[i]=y;

            add_edge(x,y,z);

            add_edge(y,x,z);

        }

        int ans=0;

        while(bfs())

        {

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

                cur[i]=head[i];

            ans+=dinic(st,INF);

        }

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

        {

            if((!dis[xx[i]] && dis[yy[i]]) || (dis[xx[i]] && !dis[yy[i]]))

            {

                printf("%d %d\n",xx[i],yy[i]);

            }

        }

        printf("\n");

    }

    return 0;

}

巴特西

UVA 10480 Sabotage (最大流) 最小割边

最新文章

热门文章