2015 icpc北京赛区 D 最小割

题目大意：给你一棵技能树，如果要学习一个技能，那么它之前的技能要全部学完，第 i 个点需要ai 能学习

每条边有一个消耗c 如果支付c那么就能去掉这条边，你还可以kejin 花费di 就能直接学习第 i 个技能，

问你最少花费多少能学习到s。

思路：这个最小割好难想啊，将每个点拆成两个点 i 和 i + n，

1. 如果i 和 j 之间有边那么 i + n 向 j 建一条流量为边的消耗的边。

2. i 和 i + n 建一条流量为 di 的边

3. S 向 i 建一条流量为 ai 的边

4. s + n 向 T 建一条流量为 inf 的边

然后跑最大流得到最小割。

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define pii pair<int,int>
#define piii pair<int, pair<int,int> >

using namespace std;

const int N = 500 + 10;
const int M = 10000 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

int n, m, s, tot, S, T, head[N << 1], level[N << 1];

struct node {
    int u, v, w, nx;
} edge[M << 2];

void add(int u, int v, int w) {
    edge[tot].u = u; edge[tot].v = v; edge[tot].w = w;
    edge[tot].nx = head[u]; head[u] = tot++;
}

bool bfs() {
    memset(level, 0, sizeof(level));
    queue<int> que;
    level[S] = 1; que.push(S);  

    while(!que.empty()) {
        int u = que.front(); que.pop();
        if(u == T) return true;

        for(int i = head[u]; ~i; i = edge[i].nx) {

            int v = edge[i].v;
            if(level[v] || edge[i].w <= 0) continue;
            level[v] = level[u] + 1;
            que.push(v);
        }
    }
    return false;
}

int dfs(int u, int p) {
    if(u == T) return p;
    int ret = 0;
    for(int i = head[u]; ~i; i = edge[i].nx) {
        int v = edge[i].v, w = edge[i].w;
        if(level[v] != level[u] + 1 || w <= 0) continue;
        int f = dfs(v, min(p - ret, w));
        ret += f;
        edge[i].w -= f;
        edge[i ^ 1].w += f;
        if(ret == p) break;
    }
    if(!ret) level[u] = 1;
    return ret;
}

int Dinic() {
    int ans = 0;
    while(bfs()) ans += dfs(S, inf);
    return ans;
}

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

int main() {
    int cas; scanf("%d", &cas);
    while(cas--) {
        scanf("%d%d%d", &n, &m, &s);
        S = 0, T = 2 * n + 1;
        init();

        for(int i = 1; i <= m; i++) {
            int u, v, w; scanf("%d%d%d", &u, &v, &w);
            add(u + n, v, w); add(v, u + n, 0);
        }

        for(int i = 1; i <= n; i++) {
            int x; scanf("%d", &x);
            add(S, i, x); add(i, S, 0);
        }

        for(int i = 1; i <= n; i++) {
            int x; scanf("%d", &x);
            add(i, i + n, x);
            add(i + n, i, 0);
        }

        add(s + n, T, inf);
        add(T, s + n, 0);
        printf("%d
", Dinic());
    }
    return 0;
}

/*
*/