Transportation

2 1 2
1 2 1 2
2 1 2
1 2 1 1
2 2 2
1 2 1 2
1 2 2 2

4
-1
3

题意：

有N个城市和M条单向路线。对于每条线路，有四个信息：起点a、终点b、费用系数c、容量d(1<=d<=5)，表示(1) 运送x单位的货物需要花费c * x * x，(二) 这条路最多能运送d单位的货物。现在问你能否将K单位货物从1运送到N，若可以输出最小花费，否则输出-1。

解析：

这题一看就是用费用流来写，但是费用流的前提是费用和流量是成正比的，但这一题费用和流量的平方成正比。所以这里要转化一下，目的是要把c * x * x 变成 c * x1 + c* x2 + ...c * xi。即把每条边拆d条边，每条边的费用为 c * xi，容量为1。这里我们就要想办法表示出xi。

根据等差公式，我们知道，n * n = 1 + 3 + 5 + … +（2n - 1)。 这就是我们要表示的xi。

转化好以后就是裸的费用流的问题了。

不太理解的可以看看这篇文章，讲的比我仔细。点我

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define maxn 110
#define maxm 100000 + 10
#define INF 0x3f3f3f3f
using namespace std;
int n, m, k;
int inset, outset;

struct node {
    int u, v, cap, flow, cost, next;
};

node edge[maxm];
int head[maxn], cnt;
int dist[maxn], vis[maxn];
int per[maxn];

void init(){
    cnt = 0;
    memset(head, -1, sizeof(head));
}

void add(int u, int v, int w, int c){
    edge[cnt].u = u;
    edge[cnt].v = v;
    edge[cnt].cap = w;
    edge[cnt].flow = 0;
    edge[cnt].cost = c;
    edge[cnt].next = head[u];
    head[u] = cnt++;
    edge[cnt].u = v;
    edge[cnt].v = u;
    edge[cnt].cap = 0;
    edge[cnt].flow = 0;
    edge[cnt].cost = -c;
    edge[cnt].next = head[v];
    head[v] = cnt++;
}

void getmap(){
    int a, b, c, d;
    outset = 0;
    inset = n + 1;
    for(int i = 1;i <= m; ++i){
        scanf("%d%d%d%d", &a, &b, &c, &d);
        for(int j = 1; j <= d; ++j){
            add(a, b, 1, (j * 2 - 1)*c);
        }
    }
    add(outset, 1, k, 0);
    add(n, inset, k, 0);
}

bool SPFA(int st, int ed){
    queue<int>q;
    for(int i = 0; i <= inset; ++i){
        dist[i] = INF;
        vis[i] = 0;
        per[i] = -1;
    }
    dist[st] = 0;
    vis[st] = 1;
    q.push(st);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for(int i = head[u]; i != -1; i = edge[i].next){
            node E = edge[i];
            if(dist[E.v] > dist[u] + E.cost && E.cap > E.flow){
                dist[E.v] = dist[u] + E.cost;
                per[E.v] = i;
                if(!vis[E.v]){
                    vis[E.v] = 1;
                    q.push(E.v);
                }
            }
        }
    }
    return per[ed] != -1;
}

void MCMF(int st, int ed, int &cost, int &flow){
    flow = 0;
    cost = 0;
    while(SPFA(st, ed)){
        int mins = INF;
        for(int i = per[ed]; i != -1; i = per[edge[i ^ 1].v]){
            mins = min(mins, edge[i].cap - edge[i].flow);
        }
        for(int i = per[ed]; i != -1; i = per[edge[i ^ 1].v]){
            edge[i].flow += mins;
            edge[i ^ 1].flow -= mins;
            cost += edge[i].cost * mins;
        }
        flow += mins;
    }
}

int main (){
    while(scanf("%d%d%d", &n, &m, &k) != EOF){
        init();
        getmap();
        int cost ,flow;
        MCMF(outset, inset, cost, flow);
        if(flow == k)
            printf("%d\n", cost);
        else
            printf("-1\n");
    }
    return 0;
}

HDU 3667-- Transportation【最小费最大流 && 拆边建图 && 经典】

原文：http://blog.csdn.net/hpuhjh/article/details/48056355