poj1459（Power Network）

浏览数：19 / 时间：2015年06月09日

题目大意：

输入分别为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 }