最小费用最大流

题意：

分析：

这是我第一次做最小费用最大流的题目。感觉还行，写个题解留作纪念。

意识到这是个关于最小费用最大流问题并不难。但是，关键在于如何建图。
拆点是一定的。我刚开始想，对每一个节点，拆成两个。原节点到拆点一条c=1 d=-vi 的路
拆点到原节点一条c=inf,d=0的路。但是这时不行的！
因为这会造成负圈！这真的太致命了。
所以，我们不能这样建图。我们可以这样建图，原节点到拆点建两条边，一条c=1,d=-vi 另一条c=inf,d=0
然后原节点到其他节点的边，都变成拆点到其他节点的边。这样我们也可以实现。
注意，这里有一个条件1<=u<v<=n 所以，我们这样做不会有负圈的。

然后造个起点，连所有的原节点，建个终点连所有拆点。
然后我们跑个最小费用最大流，再取个相反数就可以了。

代码如下：

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int, int> pii;
const int max_n = 250;
const int max_m = 1100;
const int inf = 2e9;
int n, m, k;

struct edge
{
    int to, cap, rev, cost, next;
}E[max_m * 4];
int head[max_n];
int cnt = 1;
void add(int from, int to, int cap, int cost) {
    E[cnt].to = to;E[cnt].cap = cap;
    E[cnt].cost = cost;E[cnt].rev = cnt + 1;
    E[cnt].next = head[from];head[from] = cnt++;

    E[cnt].to = from;E[cnt].cap = 0;
    E[cnt].cost = -cost;E[cnt].rev = cnt - 1;
    E[cnt].next = head[to];head[to] = cnt++;
}

int dist[max_n];
bool used[max_n];
pii fa[max_n];
bool spfa(int s,int t) {
    fill(dist, dist + max_n, inf);
    fill(used, used + max_n, false);
    dist[s] = 0;used[s] = true;
    queue<int> que;que.push(s);
    while (!que.empty()) {
        int u = que.front();que.pop();
        used[u] = false;
        for (int i = head[u];i;i = E[i].next) {
            edge& e = E[i];
            if (e.cap <= 0 || dist[e.to] <= dist[u] + e.cost)continue;
            dist[e.to] = dist[u] + e.cost;
            fa[e.to] = { u,i };
            if (used[e.to]) continue;
            que.push(e.to);
            used[e.to] = true;
        }
    }return dist[t] != inf;
}
int matchpath(int s,int t,int& f) {
    int d = f;int res = 0;
    for (int cur = t;cur != s;cur = fa[cur].first) {
        edge& e = E[fa[cur].second];
        d = min(d, e.cap);
    }
    f -= d;res += d * dist[t];
    for (int cur = t;cur != s;cur = fa[cur].first) {
        edge& e = E[fa[cur].second];
        e.cap -= d;E[e.rev].cap += d;
    }
    return res;
}
int mcf(int s,int t,int f) {
    int res = 0;int cost = 0;
    while (f > 0 && spfa(s, t)) {
        cost = matchpath(s, t, f);
        res += cost;
    }return res;
}
void init() {
    fill(head, head + max_n, false);
    cnt = 1;
}

int main() {
    ios::sync_with_stdio(0);
    int T;cin >> T;
    for (int t = 1;t <= T;t++) {
        cin >> n >> m >> k;init();
        int start = n + 1;int ed = start + 1;
        for (int i = 1;i <= n;i++) {
            int val;cin >> val;
            add(start, i, inf, 0);
            add(i, i + ed, 1, -val);
            add(i, i + ed, inf, 0);
            add(i + ed, ed, inf, 0);
        }
        for (int i = 1;i <= m;i++) {
            int u, v, cost;
            cin >> u >> v >> cost;
            add(u + ed, v, inf, cost);
        }cout << "Case #" << t << ": " << -mcf(start, ed, k) << endl;
    }
}