建图，网络流，最小费用最大流

题意：

分析：

雨神说过，图论题难就难在建图上。这题我觉得建图还是蛮难的。

我们捕捉一下重要信息：
从一个额外的点出发，恰好经过每一个点一次，可以进行跳跃，永远是小点连大点。

我们不难明白，所谓额外的点其实就是时空跳跃的中介点，也同时是起点。
同时，我们也很本能的想将所有的点向汇点t连一条c=1,d=0的有向边。
然后求最小费用最大流。
类似这样：

但是，很明显没有这么简单。
我们会发现，我们仅仅实现了从S跳到每一个节点上去。
我们都知道，在最小费用流算法中，我们是每一次都取最短路的。
我们无法保证走了一次的点不会在被取到。
也无法保证能够实现点分叉的情况。
比如图中e(1,2)于e(1,3)
假设，我们取费用流时，第一次取到了1。
然后要取2时，我们有两条路。
1.时空跳跃到2
2.从1到2
第一种尚且还好，但如果是第二种的话，那么e(s,1)的c必须>1了。
且我们的e(s,1)的d算了两次，亏了！！
这种情况无法满足

再来看下面遇到分叉的情况。
1已选，3通过e(1,3)已选，下面该是2了。因为我们已经有路s->1->3了
即在分叉点1处我们已经向3拐了，因此s->1->2是不存在的。但是，我们又怎么区分呢？

做不到啊！！

对上面两种气矿进行总结：
1.我们对于每一个节点，他关于其伸出去的枝杈只能走一个。
2.在搜寻最短路时，我们不应从最开始就开始搜，还应该增加从之前的节点开始搜索。

我们看第一点，这很简单我们可以对其进行限流如：

那第二点呢，我们的起点时始终不变的！永远是s，如果想改变只能连一条e(s,1) d=0；
因为大点是不可能到达小点的，所以我们不用担心。

这回和原来的图有些冲突，我们可以拆点来解决。

就像这样：

s点向1~n连一条c=1，d=0的边
s点向n+1·2n连一条c=1，d=传送cost
n+1·2n向t连一条c=1，d=0的边
对边e(u,v),变为e(u,v+n)c=1,d=原cost

如此这般，快乐的跑一个最小费用最大流就好了。

玄学

代码如下：

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int, int> pii;
const int inf = 2e9;
const int max_n = 2000;
const int max_m = 40000;
int n, m;
struct edge
{
    int to, cap, cost, rev, next;
}E[max_m];
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 + n + 10, inf);
    fill(used, used + n + 10, false);
    queue<int> que;dist[s] = 0;
    que.push(s);used[s] = true;
    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 (dist[e.to] <= dist[u] + e.cost || e.cap == 0)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;
    for (int i = t;i != s;i = fa[i].first) {
        int id = fa[i].second;
        d = min(d, E[id].cap);
    }for (int i = t;i != s;i = fa[i].first) {
        int id = fa[i].second;
        edge& e = E[id];
        e.cap -= d;
        E[e.rev].cap += d;
    }f -= d;
    return d * dist[t];
}
int mcf(int s,int t,int f) {
    int res = 0;int cost;
    while (f > 0 && spfa(s, t))
        res += matchpath(s, t, f);
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> m;
    int start = 2 * n + 1;int ed = start + 1;
    for (int i = 1;i <= n;i++) {
        int cost;cin >> cost;
        add(start, n + i, 1, cost);
        add(start, i, 1, 0);
        add(i + n, ed, 1, 0);
    }for (int i = 1;i <= m;i++) {
        int u, v, cost;cin >> u >> v >> cost;
        if (u > v)swap(u, v);
        add(u, v + n, 1, cost);
    }n = ed;
    cout << mcf(start, ed, n) << endl;
}