Solution

一句话题意,求一个不能割同一条路径两个边的最小割。
我们直接先按照题意建图,然后每条边都加个流量为 INF 的反向边,通过画图和简单思考可以知道,如果割了一条路径的两条边,一定会割掉一个反向边,如果割了反向边就不可能是最小割了,所以加了反向边就可以保证答案的正确性。

还有就是要特判一下如果 1 号点不能到达一个点,如果加了反向边它们就可能联通的,这时候不需要加反向边。

别忘记开 long long

Code

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define long long long
using namespace std;
const long N = 1000;
const long M = 50000;
const long INF = 100000000000005LL;
long n, m;
long u[M], v[M], w[M];
long head[N], nex[M], to[M], c[M], ce;
void add(long u, long v, long w) {
    to[++ce] = v; nex[ce] = head[u];
    head[u] = ce; c[ce] = w;
}
long d[N];
queue<long> q;
bool bfs() {
    memset(d, -1, sizeof d);
    d[1] = 0; q.push(1);
    while(!q.empty()) {
        long u = q.front(); q.pop();
        for(long i=head[u]; i; i=nex[i]) {
            long v = to[i];
            if(c[i] && d[v] == -1) {
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
    return d[n] != -1;
}
long dfs(long u, long flow) {
    if(u == n) return flow;
    long res = 0;
    for(long i=head[u]; i; i=nex[i]) {
        long v = to[i];
        if(c[i] && d[v] == d[u] + 1) {
            long tmp = dfs(v, min(flow, c[i]));
            flow -= tmp; c[i] -= tmp; res += tmp;
            if(i <= m) c[i+m] += tmp;
            else c[i-m] += tmp;
            if(flow == 0) break;
        }
    }
    if(res == 0) d[u] = -1;
    return res;
}
int main() {
    scanf("%lld%lld", &n, &m);
    for(long i=1; i<=m; i++) {
        scanf("%lld%lld%lld", &u[i], &v[i], &w[i]);
        add(u[i], v[i], w[i]);
    }
    bfs();
    for(long i=1; i<=m; i++) {
        if(d[u[i]] == -1 || d[v[i]] == -1) add(v[i], u[i], 0);
        else add(v[i], u[i], INF);
    }
    long ans = 0;
    while(bfs()) ans += dfs(1, INF);
    printf("%lld\n", ans > INF ? -1 : ans);
    return 0;
}

Description

由于 FZYZ 教学区禁止使用手机,所以如何在一个课间通知到人就成了一个很大的问题。所幸,在不知道被信息传
递不及时坑了多少次之后,小叶子(@97littleleaf11)完美地解决了这个问题。小叶子组建了一张关系网,每一个
人是这张关系网上的一个节点(节点编号为[0,n-1]),两个人之间的通讯关系就是这张网上的一条有向边(一条 u->
v 的边意味着信息可以从u 传递到 v)。小叶子是 0 号节点,也是信息的发出者,n+e 是 n-1 号节点,在这个问
题中,他就是信息的接受者。一条信息从小叶子出发,可以沿着任意的边传递,最终传递给 n+e。在这个过程中,
一个人(包括小叶子和 n+e)可以经过多次,一条边也可以经过多次。经过多年的观察,小叶子发现这张关系网的每
一条边都是有可能被hack 的!当然每条边 hack 的代价是不一样的。所以,小叶子想要评价这个关系网的安全程
度。试想你要入侵这一张关系网,那么你只能事先选择一些边,将这些边hack 掉。如果一条边被 hack 了,就意
味着当信息从这条边传递的时候就会被截获。当然 n+e 也是非常厉害的!如果一条信息在传递过程中被截获两次
及以上,那么 n+e 就能用强大的智商定位出你的位置,那么这一次入侵就必然会失败。当然,如果 n+e 接收到了
消息,但是这条消息没有被截获,那么这次入侵也就是失败的。更精确地说,一次成功的入侵要满足以下条件:对
于任意一种可能的传递信息的方式(对应着一条从 0 到 n-1 的路径),必须经过恰好一次被hack 的边。一次入侵
的代价就是你选择 hack 掉的边的代价和。小叶子想要知道,如果你拥有 n+e 这样超神的智商,而你又想最小化
代价,那么你入侵的代价会是多少呢?

Input

第一行 n,m。表示点数及边数
接下来 m 行,每行三个整数 u,v,w,表示一条从 u 到 v 的代价为 w 的边。
2<=n<=100,m<=2500,1<=w<=10^9,0<=u,v<n,保证存在至少一条从0到n-1的路径。

Output

输出一行,表示答案。,如果不存在合法的入侵方案,那么输出-1.

Sample Input

6 7
0 1 5
0 2 5
1 3 1
2 4 1
4 1 1
3 5 5
4 5 5 

Sample Output

6