网络流算法

Envyskyoung

浏览: 15875 次
性别:
来自: 长沙

最近访客更多访客>>

qq543123909

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

网络流
ACM算法

网络流算法网络流算法用于解决从源点到汇点最大流的问题。 Edmonds-Karp算法算法主要思想：每次BFS找到一条从源点到汇点的最少路径数的可行路径，同时把这条路径塞满，这条路上的最小容量即为这条路径的流量。然后将这条路径的正向边删除，增加一条容量相同的反向边，当BFS无法进行下去的时候，则算法结束，最大流为每次BFS找到的可行路径的流量和。

Poj1273 Drainage Ditches

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <iostream>
using namespace std;

int G[300][300];
bool visited[300];
int Prev[300];
int n,m;

int Augment()
{
	int v;
	bool bFindPath;
	memset(Prev,0,sizeof(Prev));
	memset(visited,0,sizeof(visited));
	deque<int> q;
	Prev[1]=0;
	visited[1]=1;
	q.push_back(1);
	bFindPath=false;
	//bfs找到从源到汇的一条路径
	while(!q.empty())
	{
		v=q.front();
		q.pop_front();
		for(int i=1;i<=m;i++)
		{
			if(G[v][i]>0 && visited[i]==0)
			{
				Prev[i]=v;
				visited[i]=1;
				
				if(i==m)
				{
					bFindPath=true;
					q.clear();
					break;
				}
				else
				{
					q.push_back(i);
				}
			}
		}
	}
	int nMinFlow=9999999;
	if(!bFindPath)
		 return 0;
	//构建新残余网络，构建增广路径
	v=m;
	while(Prev[v])
	{
		nMinFlow=min(nMinFlow,G[Prev[v]][v]);
		v=Prev[v];
	} 
	v=m;
	while(Prev[v])
	{
		G[Prev[v]][v]-=nMinFlow;
		G[v][Prev[v]]+=nMinFlow;
		v=Prev[v];
	}
	return nMinFlow;
}


int main()
{
	int s,e,c;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		memset(G,0,sizeof(G));
		for(int i=1;i<=n;i++)
		{
			scanf("%d %d %d",&s,&e,&c);
			G[s][e]+=c;
		}
		int nMaxFlow=0;
		int aug;
		while(aug=Augment()) //每次通过bfs找到一个可行路径 
		{
			nMaxFlow+=aug;
		}
		printf("%d\n",nMaxFlow);
	}
	return 0;
}

2.Dinic算法

为了少做几次bfs。

解决方法：先对结点进行分层，然后以层次数进行dfs，这样一次的增广过程可以通过dfs找到几条可行路径。结点回溯回溯到该路径的流量对应的最小层数容量边的起点。同时还要注意要将原图备份，使用原图上的边的容量减去做完最大流的残余网络上的边的剩余容量，就是边的容量。

POJ 3436 ACM Computer Factory

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstdio>
#include <string.h>
#include <stdlib.h> 
using namespace std;
#define MYMAX 120
#define INFINITE 99999999
int P, N;
int T; //汇总编号
struct Machine
{
	int Q;
	int in[12];
	int out[12];
} Machines[100];
int G[MYMAX][MYMAX]; // Machines[i] 对应于节点 i 和 i + N，两者之间连边权为Machines[i].Q
int G2[MYMAX][MYMAX]; // Machines[i] 对应于节点 i 和 i + N，两者之间连边权为Machines[i].Q
int MaxFlow;
bool MyEqual( int * s1, int * s2,int P)
{
	for( int i = 0;i < P;i ++ ) {
		if( s1[i] != s2[i] && s1[i]	!= 2 && s2[i] != 2 )
			return false;
	}
	return true;

}
int Visited[MYMAX];
int Layer[MYMAX];
bool CountLayer()
{
	deque<int> q;
	memset(Layer,0xff,sizeof(Layer));
	q.push_back(0);
	Layer[0] = 0;
	while(!q.empty()) {
		int v = q.front();
		q.pop_front();
		for( int i = 0;i <= T; i ++ ) {
			if( G[v][i] > 0 && Layer[i] == -1 ) {
				Layer[i] = Layer[v] + 1;
				if( i == T )
					return true;
				else
					q.push_back(i);
			}
		}
	}
	return false;
}
int Dinic()
{
	deque<int> q;
	int i;
	int nMaxFlow = 0;
	while( CountLayer()) {
		memset(Visited,0,sizeof(Visited));
		q.push_back(0);
		Visited[0] = 1;
		while( ! q.empty()) {
			int v = q.back();
			if( v == T ) {
				int nMinC = INFINITE,nMinC_vs;
				for( i = 1;i < q.size();i ++ ) {
					int vs = q[i-1];
					int ve = q[i];
					if( G[vs][ve] > 0 && nMinC > G[vs][ve]) {
						nMinC = G[vs][ve];
						nMinC_vs = vs;
					}
				}

				nMaxFlow += nMinC;
				for( i = 1;i < q.size();i ++ ) {
					int vs = q[i-1];
					int ve = q[i];
					G[vs][ve] -= nMinC;
					G[ve][vs] += nMinC;
				}

				while( ! q.empty() && q.back() != nMinC_vs)  {
					Visited[q.back()] = 0;	
					q.pop_back();
				}

			}
			else {
				for( i = 0;i <= T;i ++ ) {
					if( G[v][i] > 0 && Layer[i] == Layer[v] + 1 &&	! Visited[i] ) {
						Visited[i] = 1;
						q.push_back(i);
						break;
					}
				}
				if( i > T ) 
					q.pop_back();
			}
		}
	}
	return nMaxFlow;
}

int main()
{
	cin >> P >> N;//P个组件,N个机器 
	int i,j;
	memset(G,0,sizeof(G));
	for( i = 1;i <= N; i ++) {
		scanf("%d",&Machines[i].Q);
		for( j = 0; j < P; j ++ )
			scanf("%d", & Machines[i].in[j]);
		for( j = 0; j < P; j ++ )
			scanf("%d", & Machines[i].out[j]);
		G[i][i+N] = Machines[i].Q;
	}	
	
	T = 2 * N + 1; //汇点编号

	//每个机器拆成两个点 i 和 i + N，一个用于接收部件，一个用于产出
	//从i 到i + N 连边，容量 就是 Qi
	for( i = 1; i <= N ; i ++ ) {
		for( j = i + 1 ; j <= N; j ++ ) {
			if( MyEqual( Machines[i].out, Machines[j].in,P )) 
				G[i+N][j] = INFINITE;
			if( MyEqual( Machines[j].out, Machines[i].in,P )) 
				G[j+N][i] = INFINITE;
		}
		int k;
		G[0][i] = INFINITE;
		for( k = 0; k < P; k ++ )
			if( Machines[i].in[k] == 1 ) {
				G[0][i] = 0;
				break;
			}
		G[i+N][T] = INFINITE;
		for( k = 0; k < P; k ++ )
			if( Machines[i].out[k] == 0 || Machines[i].out[k] == 2 ) {
				G[i+N][T] = 0;
				break;
			}
	}
	memcpy(G2, G,sizeof(G));
	int nMaxFlow = Dinic();
	int nEdges = 0;
	for( i = N + 1; i < T;i ++ ) 
		for( j = 1; j <= N; j ++ ) 
			if( G[i][j] < G2[i][j] ) 
				nEdges ++;
	cout << nMaxFlow << " " << nEdges << endl;
	for( i = N + 1; i < T;i ++ ) 
		for( j = 1; j <= N; j ++ ) 
			if( G[i][j] < G2[i][j] ) 
				cout << i - N << " " << j << " " << G2[i][j] - G[i][j] << endl;
	
	
	return 0;
}

其他典型例题：

poj2112 Optimal Milking

Poj1149 pigs

3. 有流量下界的网络最大流处理方法：

思路：分离下界

添加新的节点X，Y，使得X，Y成为新图的源点和汇点，若新图的最大流中，源点Y的所有发出边全部被覆盖，则原图有解，否则无解。这样就转换成了普通网络流问题进行解决。

POj2396 Budget

4.最小费用最大流

每条边上多了一个输送单位流量的费用参数,在最大流中寻找一个费用最小的最大流.

POJ 2135

#include <stdio.h>
#include <queue>
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
using namespace std;

#define MAXN 1000
#define MAXM 20000

struct Edge
{
	int a,b,cost,flow;
}edge[MAXM+1];

int father[MAXN+1];
int reach[MAXN+1];
int cost[MAXN+1];
int m,n;

int FindPath(int s,int t)
{
	int ans,a,b,c,temp;
	int i;
	memset(reach, 0, sizeof(reach));
	reach[s]=1;
	cost[s]=0;
	int fix;
	fix=0;
	while(!fix)
	{
		fix=1;
		for(i=1;i<=m;i++)
		{
			a=edge[i].a;
			b=edge[i].b;
			c=edge[i].cost;
			if(edge[i].flow>0)
			{
				if(reach[b])
				{
					temp=cost[b]-c;
					if(!reach[a] || cost[a]>temp)
					{
						cost[a]=temp;
						reach[a]=1;
						father[a]=-i;
						fix=0;
					}
				}
			}
			else
			{
				if(reach[a])
				{
					temp=cost[a]+c;
					if(!reach[b] || cost[b]>temp)
					{
						cost[b]=temp;
						reach[b]=1;
						father[b]=i;
						fix=0;
					}
				}
			}
		}
	}
	if(!reach[t])
		return -1;		
	else
	{
		b=t;
		while(b!=s)
		{
			i=father[b];
			if(i>0)
			{
				edge[i].flow++;
				b=edge[i].a;
			}
			else
			{
				edge[-i].flow--;
				b=edge[-i].b;
			}
		}
	}
	return cost[t];
}
	


void Solve()
{
	int ans;
	for(int i=1;i<=m;i++)
	{
		edge[i+m].a=edge[i].b;
		edge[i+m].b=edge[i].a;
		edge[i+m].cost=edge[i].cost;
	}
	m=m+m;
	ans=FindPath(1,n)+FindPath(1,n);
	printf("%d\n",ans);
}


int main()
{
	scanf("%d %d",&n,&m);//n个点,m条边 
	for(int i=1;i<=m;i++)
		scanf("%d %d %d",&edge[i].a,&edge[i].b,&edge[i].cost);
	Solve();
	return 0;
}

分享到：

hdu 1421 搬寝室

2013-04-19 23:10
浏览 536
评论(0)
分类:编程语言
查看更多

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论