alpc60 ACM/ICPC程序设计
成长的路……源
posts - 20,comments - 42,trackbacks - 0
 

网络流

1273 Drainage Ditches

这是一道比较单纯的网络流,题目要求只要求出源点到汇点的最大流就行了,而并不需要任何的建模抽象的东西,唯一一点要注意的是,要考虑有重边的情况。

这里我用的是增广路法求的最大流,流从源点s出发,用BFS找到一条增广路径,然后找这条路径上的最小值min,对增广路进行扩展,每一次扩展会使得f[pre[i]][i]的值增大,那么它的反向路径f[i][pre[i]]的值会减小,一直进行下去,直到找不到增广路为止,算法结束。

Source

 

Problem Id:1273 User Id:linyangfei

Memory:240K Time:15MS

Language:C++ Result:Accepted

 

Source

 

#include <stdio.h>

#include <string.h>

 

int n,m,pre[205];

int f[205][205];

bool mark[205];

 

int bfs();

__int64 MaxFlow();

 

int main()

{

       int i,s,e,c;

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

       while(scanf("%d%d",&m,&n)!=EOF)

       {

              memset(f,0,sizeof(f));

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

              {

                     scanf("%d%d%d",&s,&e,&c);

                     if(f[s-1][e-1]==0)

                            f[s-1][e-1]=c;

                     else

                            f[s-1][e-1]+=c;

              }

              printf("%I64d\n",MaxFlow());

       }

       return 0;

}

 

int bfs()

{

       int q[205],qt=0,qh=1,i,x,min;

       q[qt]=0;

       mark[0]=true;

       while(qt<qh)

       {

              x=q[qt];

              if(x==n-1)

              {

                     min=100000000;

                     for(i=n-1; pre[i]!=-1; i=pre[i])

                            min=f[pre[i]][i]<min?f[pre[i]][i]:min;

                     return min;

              }

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

              {

                     if(!mark[i] && f[x][i]>0)

                     {

                            q[qh++]=i;

                            mark[i]=true;

                            pre[i]=x;

                     }

              }

              qt++;

       }

       return 0;

}

 

__int64 MaxFlow()

{

       int i,min;

       __int64 maxflow=0;

       memset(mark,0,sizeof(mark));

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

              pre[i]=-1;

       while(min=bfs())

       {

              for(i=n-1; pre[i]!=-1; i=pre[i])

              {

                     f[pre[i]][i]-=min;

                     f[i][pre[i]]+=min;

                    

              }

              maxflow+=min;

              memset(mark,0,sizeof(mark));

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

                     pre[i]=-1;

       }

       return maxflow;    

}

1149 PIGS

       也是一道很经典的网络流的题目,题目大意是MirkoM个猪圈,猪圈里面有一定数量的猪,但他没有钥匙,而只有来买猪的顾客才会有一些特定房间的钥匙,每次顾客来之前,都跟Mirko预约好,所以Mirko的任务就是找出一个计划,使他能卖出最多数量的猪。对于每位顾客,Mirko可以选择卖出猪的数量,也可以在该顾客打开的猪圈间任意调整猪的数量,每个猪圈的容量无限大。

       我觉得这个问题的一个关键点是建模,如何建立一个网络流的模型很关键。我把所有的猪圈统一看成一个大的源点S,把每个顾客看成是一个节点,然后再人工地添加一个汇点。这样可以得出下面的路径关系。

1、 在先到的顾客和后到的顾客之间有一条路径,指向后到的顾客,这条路径的容量无限大。

2、 在源点有指向各个顾客的路径,路径的容量为顾客拥有的钥匙所能打开的猪圈的猪的总量,注意,当两个顾客拥有同一把钥匙的时候,猪圈的数量只能加到一个顾客节点的路径上,不能重复加,他们之间的转移关系就靠1中两顾客间容量无限大的路径来实现。

我想有了这两点,把网络流的模型建立起来后,求解的算法按照1273的模版就应该很容易了。

#include <stdio.h>

#include <string.h>

 

const int INF=100000000;

 

int f[105][105],pig[1005],key[1005][105],pre[105];

bool mark[105];

int m,n;

 

int bfs();

int MaxFlow();

 

int main()

{

       int i,j,c,p,k;

       //将猪圈看作一个大的源点0,再外加一个汇点n+1

       freopen("1149.txt","r",stdin);

       while(scanf("%d%d",&m,&n)!=EOF)

       {

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

                     scanf("%d",&pig[i]);

              memset(f,0,sizeof(f));

              memset(key,0,sizeof(key));

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

              {

                     scanf("%d",&c);                         //每位顾客拥有钥匙的数量

                     for(j=1; j<=c; j++)

                     {

                            scanf("%d",&p);                  //输入每把钥匙的编号

                            f[0][i]+=pig[p];

                            key[p][i]=1;

                            pig[p]=0;

                     }

                     scanf("%d",&c);                         //输入每位顾客需要猪的数量

                     f[i][n+1]=c;

              }

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

                     for(j=1; j<=n; j++)

                     {

                            if(key[i][j])

                                   for(k=j+1; k<=n; k++)

                                   {

                                          if(key[i][k])

                                                 f[j][k]=INF;

                                   }

                     }

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

       }

       return 0;

}

int bfs()

{

       int q[205],qt=0,qh=1,i,x,min;

       q[qt]=0;

       mark[0]=true;

       while(qt<qh)

       {

              x=q[qt];

              if(x==n+1)

              {

                     min=100000000;

                     for(i=n+1; pre[i]!=-1; i=pre[i])

                            min=f[pre[i]][i]<min?f[pre[i]][i]:min;

                     return min;

              }

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

              {

                     if(!mark[i] && f[x][i]>0)

                     {

                            q[qh++]=i;

                            mark[i]=true;

                            pre[i]=x;

                     }

              }

              qt++;

       }

       return 0;

}

 

int MaxFlow()

{

       int i,min;

       int maxflow=0;

       memset(mark,0,sizeof(mark));

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

              pre[i]=-1;

       while(min=bfs())

       {

              for(i=n+1; pre[i]!=-1; i=pre[i])

              {

                     f[pre[i]][i]-=min;

                     f[i][pre[i]]+=min;

                    

              }

              maxflow+=min;

              memset(mark,0,sizeof(mark));

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

                     pre[i]=-1;

       }

       return maxflow;    

}

 

posted on 2007-09-22 17:09 飞飞 阅读(711) 评论(2)  编辑 收藏 引用 所属分类: ACM/ICPC

FeedBack:
# re: 网络流
2009-09-09 12:50 | yyz_max@163.com
很好很强大  回复  更多评论
  
# re: 网络流
2009-09-09 15:03 | yyz_max@163.com
看来主要是建模的问题啊  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理