当前位置:首页 > 开发 > 移动开发 > 正文

POJ-1273-Drainage Ditches

发表于: 2012-08-13   作者:aijuans   来源:转载   浏览:
摘要: POJ-1273-Drainage Ditches http://poj.org/problem?id=1273 基本的最大流,按LRJ的白书写的 #include<iostream> #include<cstring> #include<queue> using namespace std; #define INF 0x7fffffff int ma

POJ-1273-Drainage Ditches

http://poj.org/problem?id=1273

基本的最大流,按LRJ的白书写的

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define INF 0x7fffffff
int main()
{
	int n,m;
	int from,to,w,f;
	int u,v;
	int cap[201][201],flow[201][201];
	int a[201];  //起始点到每个节点的最小残量,a[i]总是正数,代替visit标记数组
	int p[201];
	queue<int>q;
	while(scanf("%d%d",&m,&n)!=EOF)
	{
		memset(cap,0,sizeof(cap));
		memset(flow,0,sizeof(flow));
		while(m--)
		{
			scanf("%d%d%d",&from,&to,&w);
			cap[from][to]+=w;
		}
		f=0;
		for(;;)
		{
			memset(a,0,sizeof(a));
			a[1]=INF;
			q.push(1);
			while(!q.empty())  //BFS找增广路
			{
				u=q.front();
				q.pop();
				for(v=1;v<=n;v++)
				if(!a[v]&&cap[u][v]>flow[u][v])
				{
					p[v]=u;  //记录v的父亲,并加入队列
					q.push(v);
					a[v]=a[u]<(cap[u][v]-flow[u][v])?a[u]:(cap[u][v]-flow[u][v]);  //最小残量
				}
			}
			if(a[n]==0)  //找不到,则当前流已经是最大流
			break;
			for(u=n;u!=1;u=p[u])  //从汇点往回走
			{
					flow[p[u]][u]+=a[n];  //更新正向流量
					flow[u][p[u]]-=a[n];  //更新反向流量
			}
			f+=a[n];  //更新从源点流出的总流量
		}
		printf("%d\n",f);
	}
	return 0;
}


更多详细信息请查看 java教程网 http://www.itchm.com/forum-59-1.html

POJ-1273-Drainage Ditches

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
1 #include<iostream> 2 /* 3 题意:就是寻找从源点到汇点的最大流! 4 要注意的是每两个点的
题目链接:http://poj.org/problem?id=1273   网络流裸题,注意有重边。重边的处理方法很简单,就
最大流首次体验感受—— 什么是最大流呢? 从一个出发点(源点),走到一个目标点(汇点),途中可
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号