River Problem

2
3
2 1 2
3 1 1
1
3 1 2 2
3
2 1 2
3 1 1
2
3 1 2 2
2 1 2 1

Case #1: -1
Case #2: 4

做这一题时参考了NOI 2008 志愿者招募 employee，我是看了这位大神的博客才懂得，建议先看这个Here

代码：

/*
思路：该题需要构建网络，用最小费用流求解。这一题花了整整一天的时间才想明白，模型隐藏得在太深了，关键在于根据流量不等式建图。

下面具体说一下建图过程。

这种题型有一个特点，就是某一个因素影响着连续的若干个位置，那么就要从中抽象出流量不等式根据流量平衡建图。

对于其中的一条边u->v( 这条边的边号为 j ，污染值为w[j] )，假设共有i种药的治理河段区间包含了这条边，也就是这i种药可以

拿来治理u->v这条河道，设这i种药使用的次数分别为Xj[1],Xj[2]...Xj[i]，

则存在不等式
        Xj[1]+Xj[2]+...+Xj[i]>=w[j]      --(a)
    成立。
这里我们引入一个增量Y[j]，将(a)简单变形得
        Xj[1]+Xj[2]+...+Xj[i]-Y[j]=w[j]   --(b)
    显然成立。
同理，我们总共可以得到n-1个这样的不等式：
        P1 = X1[1]+X1[2]+...+X1[a]-Y[1]=w[1]     --(1)           //a种药
        P2 = X2[1]+X2[2]+...+X2[b]-Y[2]=w[2]     --(2)           //b种药
                    .                         .
                    .                         .
                    .                         .
        Pj = Xj[1]+Xj[2]+...+Xj[i]-Y[j]=w[j]     --(j)           //i种药
                    .                         .
                    .                         .
                    .                         .
        Pn-2 = Xn-2[1]+Xn-2[2]+...+Xn-2[d]-Y[n-2]=w[n-2]   --(n-2) //d种药
        Pn-1= Xn-1[1]+Xn-1[2]+...+Xn-1[e]-Y[n-1]=w[n-1]   --(n-1) //e种药
注意：这里a,b,i,d,e是表示该条边有多少种药经过

然后新增一个等式，也就是增加题目里的1->n+1这条边，即增加不等式：
        Pn = 0
这样，我们得到了n个等式，把这n个当作节点。

现在建边，将上面n个等式在原图中两两相邻的相减（就是在给的有向图中相邻的两条边），又得到一系列等式，加入上式（1）和（2）相邻，则(2)-(1)得：
        P2-P1 = X2[1]+X2[2]+...+X2[b]-X1[1]-X1[2]-...-X1[a]-Y[2]+Y[1] = w[2]-w[1]
    移项得：
        w[2]-w[1]-X2[1]-X2[2]-...-X2[b]+X1[1]+X1[2]+...+X1[a]+Y[2]-Y[1] = 0     --(3)
    这个等式左边有正有负，就好比网络流中节点流量的流入流出，右边为0符合流量平衡条件，所以可以根据这个不等式建边。

    怎么建？

    （1）添加源点S和汇点T。

    （2）如果一个等式左边有非负整数c（如上式(3)中c=w[2]-w[1]），从源点S向该等式对应的顶点连接一条容量为c（这里

        定义一个全局变量all+=c，统计从源点出来的流量之和，后续用来判断是否存在可行解），权值为0的有向边；如果一

        个等式左边为负整数c，从该等式对应的顶点向汇点T连接一条容量为-c，权值为0的有向边。

    （3）如果一个变量X[i]在第j个等式中出现为-X[i]，在第k个等式中出现为X[i]，从顶点j向顶点k连接一条容量为INF，权值为c[i]的有向边。

    （4）如果一个变量Y[i]在第j个等式中出现为-Y[i]，在第k个等式中出现为Y[i]，从顶点j向顶点k连接一条容量为INF，权值为0的有向边。

这样图建好以后,求从源点S到汇点T的最小费用流，若最小流flow==all，则存在解，输出费用，否则没有解，输出-1.

*/


#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define mod 1000000009
#define INF 100000
#define pi acos(-1.0)
#define eps 1e-6
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define FRE(i,a,b)  for(i = a; i <= b; i++)
#define FREE(i,a,b) for(i = a; i >= b; i--)
#define FRL(i,a,b)  for(i = a; i < b; i++)
#define FRLL(i,a,b) for(i = a; i > b; i--)
#define mem(t, v)   memset ((t) , v, sizeof(t))
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pf          printf
#define DBG         pf("Hi\n")
typedef long long ll;
using namespace std;

const int MAXN = 10005;
const int MAXM = 1000000;

struct E        //用来存输入的那n-1条边，输入u->v,存的时候反向v->u，
{               //由题意知，最后都会汇聚到点1，我们反向建边便于dfs从1逆向访问其他点
    int u,v,w,next;
}e[MAXM];

int hed[MAXN],cnt;
int id[MAXN];   //id数组用来存边的编号，这里不用开二维的，因为仔细想想这是一个以1为根的树，但边的方向相反，所以从每个节点i出去的边只有一条
                //这样我们用id[i]就可以来唯一表示从i点出去的边了
struct Edge
{
    int to,next,cap,flow,cost;
}edge[MAXM];

int head[MAXN],tol;
int pre[MAXN],dis[MAXN];
bool vis[MAXN];
int N,n,all,m;

void init(int n)
{
    N=n;all=0;
    tol=0;cnt=0;
    memset(id,0,sizeof(id));
    memset(hed,-1,sizeof(hed));
    memset(head,-1,sizeof(head));
}

void ADD(int u,int v,int w)
{
    e[cnt].u=u;
    e[cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=hed[u];
    hed[u]=cnt++;
}

void addedge(int u,int v,int cap,int cost)
{
    edge[tol].to=v;
    edge[tol].cap=cap;
    edge[tol].cost=cost;
    edge[tol].flow=0;
    edge[tol].next=head[u];
    head[u]=tol++;
    edge[tol].to=u;
    edge[tol].cap=0;
    edge[tol].cost=-cost;
    edge[tol].flow=0;
    edge[tol].next=head[v];
    head[v]=tol++;
}

bool spfa(int s,int t)
{
    queue<int>q;
    for (int i=0;i<N;i++)
    {
        dis[i]=INF;
        vis[i]=false;
        pre[i]=-1;
    }
    dis[s]=0;
    vis[s]=true;
    q.push(s);
    while (!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=false;
        for (int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            if (edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost)
            {
                dis[v]=dis[u] + edge[i].cost;
                pre[v]=i;
                if (!vis[v])
                {
                    vis[v]=true;
                    q.push(v);
                }
            }
        }
    }
    if (pre[t]==-1) return false;
    else return true;
}

//返回的是最大流，cost存的是最小费用
int minCostMaxflow(int s,int t,int &cost)
{
    int flow=0;
    cost=0;
    while (spfa(s,t))
    {
        int Min=INF;
        for (int i=pre[t];i!=-1;i=pre[edge[i^1].to])
        {
            if (Min > edge[i].cap-edge[i].flow)
                Min=edge[i].cap-edge[i].flow;
        }
        for (int i=pre[t];i!=-1;i=pre[edge[i^1].to])
        {
            edge[i].flow+=Min;
            edge[i^1].flow-=Min;
            cost+=edge[i].cost*Min;
        }
        flow+=Min;
    }
    return flow;
}

void dfs(int u,int pre_w)   //dfs从1遍历全图，u是当前节点，pre_w是上一条边的污染值
{
    int sum=0;
    for (int i=hed[u];~i;i=e[i].next)
    {
        int v=e[i].v;
        dfs(v,e[i].w);
        sum+=e[i].w;
        addedge(id[u],id[v],INF,0);
    }
    int cc=pre_w-sum;
    if (cc>0)
    {
        addedge(0,id[u],cc,0);
        all+=cc;
    }
    if (cc<0)
        addedge(id[u],n+1,-cc,0);
    return ;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("C:/Users/asus1/Desktop/IN.txt","r",stdin);
#endif
    int i,j,T,u,v,w,l,c,cas=0;
    sf(T);
    while (T--)
    {
        sf(n);
        init(n+2);
        FRL(i,1,n)
        {
            sfff(u,v,w);
            ADD(v,u,w);      //把边的方向反过来建边
            id[u]=i;        //记录边号
        }

        ADD(n+1,1,0);       //因为所有河流都会汇聚到1，那么在原图中加一条1->n+1的边
        id[1]=n;

        dfs(1,0);

        sf(m);
        FRE(i,1,m)
        {
            scanf("%d%d%d%d",&u,&v,&l,&c);
            addedge(id[u],id[v],l,c);
        }

        int x,ans;
        x=minCostMaxflow(0,n+1,ans);
        pf("Case #%d: ",++cas);
        if (x==all)
            pf("%d\n",ans);
        else
            pf("-1\n");
    }
    return 0;
}

River Problem （hdu 3947 流量等式建图 难题 最小费用最大流）

原文：http://blog.csdn.net/u014422052/article/details/46845907