POJ 1459 Power Network 网络流基础题
题意:
输入:N个点,N1个发电厂,N2个用电厂,M条路。
输入M条路,s,e,l.代表点s-e的容量是l。
输入N1个发电厂,s,l.代表s产生l的电。
输入N2个用电产,s,l,代表s用掉l的电。
Sample Input
2 1 1 2 (0,1)20 (1,0)10 (0)15 (1)207 2 3 13 (0,0)1 (0,1)2 (0,2)5 (1,0)1 (1,2)8 (2,3)1 (2,4)7 (3,5)2 (3,6)5 (4,2)7 (4,3)5 (4,5)1 (6,0)5 (0)5 (1)2 (3)2 (4)1 (5)4
Sample Output
156
输入各种恶心。。。
思路:
网络流,最大流的模版题,今天刚开始看,学了一种新算法。Edmonds_Karp(),具体见http://blog.csdn.net/kdqzzxxcc/article/details/7881169
这道题还有一个需要处理的就是源点和汇点,因为有多源点和汇点,所以可以将0和N+1看成一个超级源点和超级汇点即可。
#include <iostream>#include <cstdio>#include <algorithm>#include <string>#include <cmath>#include <cstring>#include <queue>#include <set>#include <vector>#include <stack>#include <map>#include <iomanip>#define PI acos(-1.0)#define Max 105#define inf 1<<28#define LL(x) (x<<1)#define RR(x)(x<<1|1)using namespace std;int Map[Max][Max];int flow[Max];int start,end;int path[Max];int q[Max*100];int bfs(){ int n=end; flow[start]=inf; memset(path,-1,sizeof(path)); path[start]=start; int num=0,cnt=0; q[num++]=start; while(num>cnt) { int temp=q[cnt++]; if(temp==end)break; for(int i=0;i<=n;i++) { if(path[i]==-1&&Map[temp][i]) { flow[i]=min(flow[temp],Map[temp][i]); q[num++]=i; path[i]=temp; } } } if(path[end]==-1)return -1; return flow[end];}int Edmonds_Karp(){ int max_flow=0,step,pre,now; while(1) { step=bfs(); if(step==-1)return max_flow; now=end; max_flow+=step; while(now!=start) { pre=path[now]; Map[pre][now]-=step; Map[now][pre]+=step; now=pre; } }}int main(){ int i,j,k,l,m,n1,n2,n; int s,e; while(scanf("%d %d %d %d",&n,&n1,&n2,&m)!=EOF) { memset(Map,0,sizeof(Map)); while(m--) { scanf(" (%d,%d)%d",&s,&e,&l); Map[s+1][e+1]=l; } while(n1--)//将0看成超级源点 { scanf(" (%d)%d",&s,&l); Map[0][s+1]=l; } while(n2--)//将N+1看成超级汇点 { scanf(" (%d)%d",&s,&l); Map[s+1][n+1]=l; } start=0; end=n+1; printf("%d\n",Edmonds_Karp()); } return 0;}继续研究网络流。。