hdu 4780 13杭州K题 费用流

很显然这题是最小费用最大流， 糖果C的数量是流量， 给出的时间是为了建边用的，费用就是题目给出的费用。

设S为源点，T为汇点，先构造一排C3点，向T连，控制流出。怎么设置流入是本题的关键，我们抓住机器和糖果的关系，发现机器造第一颗糖果时，选择机器不同费用也是不同，但如果机器造第二颗糖果及以后，不管选那台机器费用都是等价的（这一过程糖果间的切换只取决于两个糖果的标号）。所以对于流入， 机器生产的第一颗糖果会流入机器，其它都不会经过机器，且用于糖果之间的切换，糖果之间的切换可以类似地理解成一个二分图。

我们设经过机器的后糖果点阵C2, 没有经过的设为C1, 机器点阵设为M，那么可以这么建图

S----> M ---->C2 ----> C3---->T S---->C1---->C3---->T，至于每条边费用的计算应该不难吧。

#include   
#include   
#include   
#include   
using namespace std;  
const int maxn = 404;  
typedef pair pii;  
const int inf = 1e9;  
int n, m, k;  
int s[103], t[103];  
int c[103][103], d[103][103], e[103][103], f[103][103];  
struct Edge {  
    int u, v, c, w, next;  
    Edge(int u, int v, int c, int w, int next):  
        u(u), v(v), c(c), w(w), next(next){}  
    Edge(){}  
}edge[100005];  
int head[maxn], E;  
void init() {  
    memset(head, -1, sizeof(head));  
    E = 0;  
}  
void add(int s, int t, int c, int w) {  
    edge[E] = Edge(s, t, c, w, head[s]);  
    head[s] = E++;  
    edge[E] = Edge(t, s, 0, -w, head[t]);  
    head[t] = E++;  
}  
int S, T;  
int pre[maxn], dis[maxn];  
bool vis[maxn];  
bool spfa(int s, int t, int n) {  
    int i, u, v;  
    for(i = 0; i <= n; i++)  
        dis[i] = inf, pre[i] = -1, vis[i] = false;  
    queue  q;  
    vis[s] = true;  
    dis[s] = 0;  
    q.push(s);  
    while(!q.empty()) {  
        u = q.front();  
        q.pop();  
        vis[u] = false;  
        for(i = head[u]; ~i; i = edge[i].next) {  
            v = edge[i].v;  
            if(edge[i].c && dis[v] > dis[u] + edge[i].w) {  
                dis[v] = dis[u] + edge[i].w;  
                pre[v] = i;  
                if(!vis[v]) {  
                    vis[v] = true;  
                    q.push(v);  
                }  
            }  
        }  
    }  
    if(dis[t] == inf) return 0;  
    return 1;  
}  
int ans;  
pair mcmf(int s, int t, int n) {  
    int aug, minc = 0, i, maxf = 0;  
    while(spfa(s, t, n)) {  
        aug = inf+1;  
        for(i = pre[t]; ~i; i = pre[edge[i].u])  
            aug = min(aug, edge[i].c);  
        for(i = pre[t]; ~i; i = pre[edge[i].u]) {  
            edge[i].c -= aug;  
            edge[i^1].c += aug;  
        }  
        maxf += aug;  
        minc += dis[t]*aug;  
    }  
    return make_pair(minc, maxf);  
}  
void debug(int n) {  
    int i, j;  
    puts("~~~~~~~~~~~~~~~~");  
    for(i = 0; i < n; i++) {  
        printf("i = %d\n", i);  
        for(j = head[i]; ~j; j = edge[j].next) if(edge[j].c)  
            printf("v = %d c = %d w = %d\n", edge[j].v, edge[j].c, edge[j].w);  
    }  
}  
int main() {  
    int i, j;  
    while(~scanf("%d%d%d", &n, &m, &k) && n && m && k) {  
        for(i = 0; i < n; i++)  
            scanf("%d%d", &s[i], &t[i]);  
        for(i = 0; i < n; i++)  
            for(j = 0; j < m; j++)  
                scanf("%d", &c[i][j]);  
        for(i = 0; i < n; i++)  
            for(j = 0; j < m; j++)  
                scanf("%d", &d[i][j]);  
        for(i = 0; i < n; i++)  
            for(j = 0; j < n;j++)  
                scanf("%d", &e[i][j]);  
        for(i = 0; i < n; i++)  
            for(j = 0; j < n; j++)  
                scanf("%d", &f[i][j]);  
        init();  
        S = n*3+m; T = S+1;  
        for(i = 0; i < n; i++)  
            add(S, i, 1, 0);  
        for(i = 0; i < m; i++)  
            add(S, i+3*n, 1, 0);  
  
        for(i = 0; i < n; i++)  
            add(i+2*n, T, 1, 0);  
  
        for(i = 0; i < n; i++)  
            add(i+n, i+2*n, 1, 0);  
  
        for(i = 0; i < n; i++)  
            for(j = 0; j < n; j++) if(i != j){  
                if(t[i] + e[i][j] >





= t[j]) continue;  
                int tp = f[i][j]+max(0, t[i] + e[i][j]-s[j])*k;  
                add(i, j+2*n, 1, tp);  
            }  
  
        for(j = 0; j < m; j++)  
            for(i = 0; i < n; i++) {  
                if(c[i][j] >= t[i]) continue;  
                int tp = d[i][j]+max(0, c[i][j]-s[i])*k;  
                add(j+3*n, i+n, 1, tp);  
            }  
    //    debug(T+1);  
        pair ans = mcmf(S, T, T+1);  
    //    printf("%d~~~~~\n", ans.second);  
        if(ans.second == n) printf("%d\n", ans.first);  
        else puts("-1");  
    }  
    return 0;  
}