POJ 1459 Power Network

题意：有n个据点，np个发电机。nc个用户，m条电线。给出发电机。用户。电线的电流限制，求最大网络电流。

这是带节点的网络流。事实上和原来没什么差别，仅仅要在前后都添加一个据点，在这里我加了0和n+1两个节点，而发电机节点的电流限制能够

转化为0->节点的电流限制，用户节点电流的限制能够转化为节点->n+1的电流限制，之后套用最大网络流模板就可以。这里我写了，Edmonds_karp算法。

稍后传上Dinic算法。。。

。

。

。。。。。。。。。。。。。

。。

AC代码例如以下：

Edmonds_karp算法

#include 
#include 
#include 
#include 
#define min(a,b) (a q;
    int a,b;
    for(i=0;i0)
            {
                f[i]=min(map[b][i],f[b]);
                p[i]=b;
                q.push(i);
            }
        }
    }
    if(p[e]==-1)
        return -1;
    else return f[e];
}

int maxflow(int s,int e)
{
    int i,j;
    int a,ans=0;
    a=Edmonds_karp(s,e);
    while(a!=-1)
    {
        int k=e,min=inf;
        while(k!=s)
        {
            map[p[k]][k]-=a;
            map[k][p[k]]+=a;
            k=p[k];
        }
        ans+=a;
        a=Edmonds_karp(s,e);
    }
    return ans;
}


int main()
{
    int i,j;
    int a,b,c,d,f;
    char z,x,y;
    while(cin>>n>>np>>nc>>m)
    {
        memset(map,0,sizeof map);
        for(i=1;i>z>>a>>x>>b>>y>>c;
            map[a+1][b+1]+=c;
        }
        for(i=1;i>z>>d>>x>>f;
            map[0][d+1]+=f;
        }
        for(i=1;i>z>>d>>x>>f;
            map[d+1][n+1]+=f;
        }
        cout
Dinic算法


#include
#include
#include
#include
#define inf 100000000
#define min(a,b) (a q;
    int a,b;
    memset(cs,-1,sizeof cs);
    cs[0]=0;
    q.push(0);
    while(!q.empty())
    {
        b=q.front ();
        q.pop();

        for(i=0;i0)
            {
                cs[i]=cs[b]+1;
                q.push(i);
            }
        }
    }
    if(cs[n+1]==-1)
        return 0;
    else return 1;

}

int dfs(int s,int mf)
{
    int i,j;
    int a,b;
    if(s==n+1)
        return mf;
    for(i=0;i0&&(a=dfs(i,min(mf,map[s][i]))))
        {
            map[s][i]-=a;
            map[i][s]+=a;
            return a;
        }
    }
    return 0;
}

int main()
{
    int i,j;
    int a,b,c,d,f;
    while(cin>>n>>np>>nc>>m)
    {
        memset(map,0,sizeof map);
        for(i=1;i