POJ 1459 Power Network （多源點/匯點最大流問題）

POJ 1459 Power Network （多源點/匯點最大流問題）

題目給你一大段解釋，其實就是廢話。還給了一張解釋圖，其實就是誤導。

題目大意：對於一個電力網來說，既有發電站，也有用電方，還有輸電線路。其中發電站是有限度的，用電方也是有限度的，輸電線更是有限度的，所以明顯一個網絡流問題。先給出線路和限度，再給出用電方，最後後出發電站。

因為是多源點（多個發電站），多匯點（多個用電方），所以需要超級源處理。

多為超級源，就是假設有一個源，連向所有的源點（發電站），其線路容量就是發電站的限度，那麼就可以把發電站當做普通點處理。再假設一個超級匯點，那麼就可以把所有匯點（用電方）連向這個超級匯點，其線路容量是用電方限度，那麼，就變成一個單純的單源點，單匯點的最大流問題。用dinic便可以解決。

#include 
#include
#include 
#include 
#include
#include
#define MAX 999999

using namespace std;

int map_[200][200];
int dis[200];
int bfs(int s,int t)
{
    int now;
    memset(dis,-1,sizeof (dis));
    dis[s] = 0;
    queue que;
    que.push(s);

    while(!que.empty())
    {
        now = que.front();
        que.pop();

        for (int i = 0;i <= t;i++)
            if (dis[i] == -1 && map_[now][i] > 0)
            {
                dis[i] = dis[now] + 1;

                que.push(i);
            }
    }

    if (dis[t] != -1)
        return 1;

    return 0;
}

int dinic(int s,int t,int x)
{
    if (s == t)
        return x;

    int tmp = x;
    for (int i = 0;i <= t;i++)
    {
        if (dis[i] == dis[s] + 1 && map_[s][i] > 0)
        {
            int imin = dinic(i,t,min(map_[s][i],x));

            map_[s][i] -= imin;
            map_[i][s] += imin;
            x -= imin;
        }
    }

    return tmp - x;
}

int main()
{
    int n,np,nc,m;

    while (~scanf (%d%d%d%d,&n,&np,&nc,&m))
    {
        int i,k;
        int u,v,c;
        memset(map_,0,sizeof(map_));
        for (i = 0;i < m;i++)
        {
            scanf( (%d,%d)%d,&u,&v,&c);
            map_[u + 1][v + 1] += c;    //0是超級源點，其他點後移
        }

         for(i = 0;i < np;i++)
        {
            scanf( (%d)%d,&v,&c);
            map_[0][v + 1] += c;
        }

        for(i = 0;i < nc;i++)
        {
            scanf( (%d)%d,&u,&c);
            map_[u + 1][n + 1] += c;
        }

        int ans = 0;

        while (bfs(0,n + 1))
            ans += dinic(0,n + 1,MAX);

        printf (%d
,ans);
    }
    return 0;
}