POJ 1459-Power Network（最大流-Edmond-Karp算法）

曾经终败给现在 2022-07-12 05:24 112阅读 0赞

Power Network

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;2000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;32768K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;27758</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;14435</td> 
  </tr> 
 </tbody> 
</table>

Description

A power network consists of nodes (power stations, consumers and dispatchers) connected by power transport lines. A node u may be supplied with an amount s(u) >= 0 of power, may produce an amount 0 <= p(u) <= p max(u) of power, may consume an amount 0 <= c(u) <= min(s(u),c max(u)) of power, and may deliver an amount d(u)=s(u)+p(u)-c(u) of power. The following restrictions apply: c(u)=0 for any power station, p(u)=0 for any consumer, and p(u)=c(u)=0 for any dispatcher. There is at most one power transport line (u,v) from a node u to a node v in the net; it transports an amount 0 <= l(u,v) <= l max(u,v) of power delivered by u to v. Let Con=Σ uc(u) be the power consumed in the net. The problem is to compute the maximum value of Con.  
![1459_1.jpg][]  
An example is in figure 1. The label x/y of power station u shows that p(u)=x and p max(u)=y. The label x/y of consumer u shows that c(u)=x and c max(u)=y. The label x/y of power transport line (u,v) shows that l(u,v)=x and l max(u,v)=y. The power consumed is Con=6. Notice that there are other possible states of the network but the value of Con cannot exceed 6.

Input

There are several data sets in the input. Each data set encodes a power network. It starts with four integers: 0 <= n <= 100 (nodes), 0 <= np <= n (power stations), 0 <= nc <= n (consumers), and 0 <= m <= n^2 (power transport lines). Follow m data triplets (u,v)z, where u and v are node identifiers (starting from 0) and 0 <= z <= 1000 is the value of l max(u,v). Follow np doublets (u)z, where u is the identifier of a power station and 0 <= z <= 10000 is the value of p max(u). The data set ends with nc doublets (u)z, where u is the identifier of a consumer and 0 <= z <= 10000 is the value of c max(u). All input numbers are integers. Except the (u,v)z triplets and the (u)z doublets, which do not contain white spaces, white spaces can occur freely in input. Input data terminate with an end of file and are correct.

Output

For each data set from the input, the program prints on the standard output the maximum amount of power that can be consumed in the corresponding network. Each result has an integral value and is printed from the beginning of a separate line.

Sample Input

2 1 1 2 (0,1)20 (1,0)10 (0)15 (1)20
    7 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

15
    6

Hint

The sample input contains two data sets. The first data set encodes a network with 2 nodes, power station 0 with pmax(0)=15 and consumer 1 with cmax(1)=20, and 2 power transport lines with lmax(0,1)=20 and lmax(1,0)=10. The maximum value of Con is 15. The second data set encodes the network from figure 1.

Source

[Southeastern Europe 2003][]

## 题目意思： ##

网络有N个点，可能是发电站，消耗站或调度器。

其中有NP个发电站提供电，NC个消耗站消耗电，调度站不提供也不消耗电，M条单向线路。

先给出M条单向线路的（U,V）Z，表示站U到站V传输的最大功率是Z；

再给出NP个发电站的（U）Z，表示发电站U提供的最大功率是Z；

最后给出NC个消耗站的（U）Z，表示消耗站U消耗的最大功率是Z。

求这个网络能够消耗的最大功率。

## 解题思路： ##

增加一个超级源点0，用于将发电站提供的电表示为发电站从超级源点得到电，即超级源点到发电站传输的最大功率是发电站U提供的最大功率；

增加一个超级汇点N+1，用于将消耗站消耗的电表示为消耗站向超级汇点输出电，即消耗站到超级汇点传输的最大功率是消耗站U消耗的最大功率。

然后使用Edmond-Karp算法，求出超级源点到超级汇点的最大流。

#include<iostream>
    #include<cstdio>
    #include<iomanip>
    #include<cmath>
    #include<cstdlib>
    #include<cstring>
    #include<map>
    #include<algorithm>
    #include<vector>
    #include<queue>
    using namespace std;
    #define INF 0xfffffff
    #define MAXN 201
    int maxData = 0x7fffffff;
    int capacity[MAXN][MAXN]; //记录残留网络的容量
    int flow[MAXN];           //标记从源点到当前节点实际还剩多少流量可用
    int pre[MAXN];            //标记在这条路径上当前节点的前驱,同时标记该节点是否在队列中
    int n,np,nc,m;            //总结点数、发电站、消耗器和线路数
    queue<int> myqueue;
    int BFS(int src,int des)
    {
        int i;
        while(!myqueue.empty())       //队列清空
            myqueue.pop();
        for(i=0; i<=n+1; ++i)
        {
            pre[i]=-1;
        }
        pre[src]=0;
        flow[src]= maxData;
        myqueue.push(src);
        while(!myqueue.empty())
        {
            int index = myqueue.front();
            myqueue.pop();
            if(index == des)            //找到了增广路径
                break;
            for(i=0; i<=n+1; ++i)
            {
                if(i!=src && capacity[index][i]>0 && pre[i]==-1)
                {
                    pre[i] = index; //记录前驱
                    flow[i] = min(capacity[index][i],flow[index]);   //关键：迭代的找到增量
                    myqueue.push(i);
                }
            }
        }
        if(pre[des]==-1)      //残留图中不再存在增广路径
            return -1;
        else
            return flow[des];
    }
    int maxFlow(int src,int des)
    {
        int increasement= 0;
        int sumflow = 0;
        while((increasement=BFS(src,des))!=-1)
        {
            int k = des;          //利用前驱寻找路径
            while(k!=src)
            {
                int last = pre[k];
                capacity[last][k] -= increasement; //改变正向边的容量
                capacity[k][last] += increasement; //改变反向边的容量
                k = last;
            }
            sumflow += increasement;
        }
        return sumflow;
    }
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("F:/cb/read.txt","r",stdin);
        //freopen("F:/cb/out.txt","w",stdout);
    #endif
        ios::sync_with_stdio(false);
        cin.tie(0);
        int i;
        int start,end,ci;
        while(cin>>n>>np>>nc>>m)
        {
            char c;
            memset(capacity,0,sizeof(capacity));
            memset(flow,0,sizeof(flow));
            for(i=0; i<m; ++i)
            {
                cin>>c>>start>>c>>end>>c>>ci;
                ++start,++end;
                capacity[start][end]+=ci;//此处注意可能出现多条同一起点终点的情况
            }
            for(i=0; i<np; ++i) //超级源点0
            {
                cin>>c>>end>>c>>ci;
                ++end;
                capacity[0][end]+=ci;
            }
            for(i=0; i<nc; ++i) //超级汇点n+1
            {
                cin>>c>>start>>c>>ci;
                ++start;
                capacity[start][n+1]+=ci;
            }
            cout<<maxFlow(0,n+1)<<endl;
        }
        return 0;
    }
    /*
    2 1 1 2 (0,1)20 (1,0)10 (0)15 (1)20
    7 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
    */

[1459_1.jpg]: /images/20220711/38b0dfd5e8b94dc5881e316c992440c4.png
[Southeastern Europe 2003]: http://poj.org/searchproblem?field=source&key=Southeastern+Europe+2003