题目地址:Power Network
题目大意:
输入分别为m个点,a个发电站,b个用户,n条边;接下去是n条边的信息(u,v)cost,cost表示边(u,v)的最大流量;a个发电站的信息(u)cost,cost表示发电站u能提供的最大流量;b个用户的信息(v)cost,cost表示每个用户v能接受的最大流量。
求发电站流向用户的最大流量。
解题思路:
最大流问题
,首先建图,我让m+1这个节点为源点S,让m这个点为汇点T。求流入T的最大流即可。
代码:
1 #include <algorithm> 2 #include <iostream> 3 #include <sstream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <string> 8 #include <bitset> 9 #include <vector> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <list> 14 //#include <map> 15 #include <set> 16 using namespace std; 17 /***************************************/ 18 #define ll long long 19 #define int64 __int64 20 /***************************************/ 21 const int INF = 0x7f7f7f7f; 22 const double eps = 1e-8; 23 const double PIE=acos(-1.0); 24 const int d1x[]= {-1,1,0,0}; 25 const int d1y[]= {0,0,-1,1}; 26 const int d2x[]= {0,-1,0,1}; 27 const int d2y[]= {1,0,-1,0}; 28 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 29 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 30 /***************************************/ 31 void openfile() 32 { 33 freopen("data.in","rb",stdin); 34 freopen("data.out","wb",stdout); 35 } 36 /**********************华丽丽的分割线,以上为模板部分*****************/ 37 #define arraysize 201 38 int maxData = 0x7fffffff; 39 int map[arraysize][arraysize]; //记录残留网络的容量 40 int flow[arraysize]; //标记从源点到当前节点实际还剩多少流量可用 41 int pre[arraysize]; //标记在这条路径上当前节点的前驱,同时标记该节点是否在队列中 42 int n,m,np,nc; 43 queue<int> myqueue; 44 int BFS(int src,int des) 45 { 46 int i,j; 47 while(!myqueue.empty()) //队列清空 48 myqueue.pop(); 49 for(i=0;i<m+1;++i) 50 { 51 pre[i]=-1; 52 } 53 pre[src]=0; 54 flow[src]= maxData; 55 myqueue.push(src); 56 while(!myqueue.empty()) 57 { 58 int index = myqueue.front(); 59 myqueue.pop(); 60 if(index==des) //找到了增广路径 61 break; 62 for(i=0;i<m+1;++i) 63 { 64 if(i!=src && map[index][i]>0 && pre[i]==-1) 65 { 66 pre[i] = index; //记录前驱 67 flow[i] = min(map[index][i],flow[index]); //关键:迭代的找到增量 68 myqueue.push(i); 69 } 70 } 71 } 72 if(pre[des]==-1) //残留图中不再存在增广路径 73 return -1; 74 else 75 return flow[des]; 76 } 77 int maxFlow(int src,int des) 78 { 79 int increasement=0; 80 int sumflow=0; 81 while((increasement=BFS(src,des))!=-1) 82 { 83 int k = des; //利用前驱寻找路径 84 while(k!=src) 85 { 86 int last = pre[k]; 87 map[last][k]-=increasement; //改变正向边的容量 88 map[k][last]+=increasement; //改变反向边的容量 89 k=last; 90 } 91 sumflow+=increasement; 92 } 93 return sumflow; 94 } 95 int main() 96 { 97 int i,j; 98 int start,end,cost; 99 while(scanf("%d%d%d%d",&m,&np,&nc,&n)!=EOF) 100 { 101 memset(map,0,sizeof(map)); 102 memset(flow,0,sizeof(flow)); 103 char c[10]; 104 for(i=0;i<n;++i) 105 { 106 scanf("%s",c); 107 sscanf(c,"(%d,%d)%d",&start,&end,&cost); 108 if(start==end) //考虑起点终点相同的情况 109 continue; 110 map[start][end]+=cost; //此处注意可能出现多条同一起点终点的情况 111 } 112 for(i=0;i<np;i++) 113 { 114 scanf("%s",c); 115 sscanf(c,"(%d)%d",&start,&cost); 116 map[m+1][start]=cost; 117 } 118 for(i=0;i<nc;i++) 119 { 120 scanf("%s",c); 121 sscanf(c,"(%d)%d",&end,&cost); 122 map[end][m]=cost; 123 } 124 cout<<maxFlow(m+1,m)<<endl; 125 } 126 return 0; 127 }