VC驿站

 找回密码
 加入驿站

QQ登录

只需一步,快速开始

搜索
查看: 730|回复: 0

[交流] 新人报道来个网络流

[复制链接]
35_avatar_middle
在线会员 发表于 2017-5-21 11:17:42 | 显示全部楼层 |阅读模式
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#include <map>  
#include <set>  
using namespace std;
const int N=201;  
const int INF=99999999; //无限大
int s,t,n,m,sum;
int flow[N][N],cap[N][N],a[N],p[N]; //分别为:flow[u][v]为<u,v>流量、cap[u][v]为<u,v>容量、a[i]表示源点s到节点i的路径上的最小残留量、p[i]记录i的前驱
int min(int a,int b)  
{  
return a<=b?a:b;  
}  
void han()
{
        int v,u,i;
        queue<int>q;//建立队列进行BFS ,进行查找 增广路。
        while(1)  //一直循环直到达到break的条件
{  
   memset(a,0,sizeof(a));//每找一次,初始化一次 ,对新的图不断进行初始化和增广
   a[s]=INF;  //将原点设置为无限大
   q.push(s);//源点入队 ,开始了bfs
   while(!q.empty())  //???当队列不为空的时候进行
   {   u=q.front();  //将队首元素附为u
    q.pop();  //队列首项出来
    for(v=1;v<=m;v++) //
    {  
     if(!a[v]&&flow[u][v]<cap[u][v])  //如果a[v]==0且从u到v的容量大于流量
     {  
      p[v]=u;  //
      q.push(v); // 把v加入队列中
      a[v]=min(a[u],cap[u][v]-flow[u][v]);//s-v路径上的最小残量  
     }  
    }  
   }

if(a[m]==0)//找不到增广路,则当前流已经是最大流  
   
         break;  

   sum+=a[m];//流加上  
   for(i=m;i!=s;i=p[i])// //从汇点顺着这条增广路往回走  
   {  
    flow[p[i]][i]+=a[m];//更新正向流量  
    flow[i][p[i]]-=a[m];//更新反向流量  
   }  
}  
printf("%d\n",sum);  
  
}
int main()
{
  int v,u,w;  
        while(scanf("%d%d",&n,&m)!=EOF)  
    {  
       s=1;//从1开始  
       t=m;//m为汇点  
       sum=0;//记录最大流量  
       memset(flow,0,sizeof(flow));//初始化  
       memset(cap,0,sizeof(cap));  
       while(n--)  
       {  
        scanf("%d%d%d",&u,&v,&w);  
        cap[u][v]+=w;//注意图中可能出现相同的边  
       }  
       han();  
    }  

       
       
        return 0;
}












上一篇:有了这个,初学者再也不怕没有练手的小项目了
下一篇:数据结构基础-线性表与模板类
您需要登录后才可以回帖 登录 | 加入驿站 qq_login

本版积分规则

关闭

站长提醒上一条 /2 下一条

QQ|小黑屋|手机版|VC驿站 ( 辽ICP备09019393号tongdun|网站地图wx_jqr

GMT+8, 2019-3-20 01:53

Powered by Discuz! X3.4

© 2009-2019 cctry.com

快速回复 返回顶部 返回列表