题目

Description

The empire is under attack again. The general of empire is planning to defend his castle. The land can be seen as N towns and M roads, and each road has the same length and connects two towns. The town numbered 1 is where general's castle is located, and the town numbered N is where the enemies are staying. The general supposes that the enemies would choose a shortest path. He knows his army is not ready to fight and he needs more time. Consequently he decides to put some barricades on some roads to slow down his enemies. Now, he asks you to find a way to set these barricades to make sure the enemies would meet at least one of them. Moreover, the barricade on the i-th road requires wi units of wood. Because of lacking resources, you need to use as less wood as possible.

Input

The first line of input contains an integer t, then t test cases follow.
For each test case, in the first line there are two integers N(N≤1000) and M(M≤10000).
The i-the line of the next M lines describes the i-th edge with three integers u,v and w where 0≤w≤1000 denoting an edge between u and v of barricade cost w.

Output

For each test cases, output the minimum wood cost.

Sample Input

1
4 4
1 2 1
2 4 2
3 1 3
4 3 4

Sample Output

4

题解

在 1~n 的最短路上,删除权值和最少的边,使 1 和 n 在两个连通分量中

分开来看,删除尽可能少的边将两个点分到两个连通分量中,是 最小割问题
而又要是最短路的边,因此应该先求一次最短路,保证处理 网络流 时,只有最短路中的边

因此该问题为 找出一个无向图中最短路中的边,建立网络流,求取最小割

由于 最小割等于最大流 因此可以转化为求 最大流问题

第一步,由于每条路的长度都是确定的(看作 1 )
因此只需要使用普通的 BFS 即可求出每个点到起点的最短距离
如果一个边的两个端点距离起点(源)的距离差不是 1 ,那么说明这条边不是最短路中的边
将剩下的边建立网络流即可(有最短路的边,也有死路对连同无影响的边)

在网络流中,根据每个边的权值求取 1~n 的最小割(根据每个边的流量求取 1~n 的最大流)

求取最大流有 Ford-Fulkerson 、 Edmonds-Karp 和 Dicin
使用 基于分层思想的网络流算法的 Dinic 算法 来解决最大流问题

直接套用模板即可

代码

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <functional>

using namespace std;

typedef long long LL;

const int INF = 0x7FFFFFFF/2;
const double eps = 1e-10;

const int maxn = 1005;
const int maxm = 10005 * 2;

struct Edge {
    int u,v,w;
    Edge():u(0),v(0),w(0) {}
    Edge(int a,int b,int c):u(a),v(b),w(c) {}
};

int pos;
Edge edge[maxm],road[maxm];
list<int> L[maxn];

int n,m;

queue<int> Q;
int dist[maxn];
bool vis[maxn];

void init() {
    pos = 0;
    for(int i = 1;i <= n;i++)
        L[i].clear();
}

//图中增加 u→v 权重为 w 的边
inline void add(int u,int v,int w) {
    edge[pos] = Edge(u,v,w);

    L[u].push_back(pos);
    pos++;
}

//Dinic
bool bfs(int s,int t) {
    memset(dist,0,sizeof(dist));
    while(!Q.empty())
        Q.pop();

    Q.push(s);
    dist[s] = 1;
    while(!Q.empty()) {
        int u = Q.front();
        Q.pop();

        for(list<int>::iterator it = L[u].begin();it != L[u].end();it++) {
            int v = edge[*it].v;
            if(!dist[v] && edge[*it].w) {
                dist[v] = dist[u] + 1;
                if(v == t)
                    return true;
                Q.push(v);
            }
        }
    }
    return false;
}
int dfs(int u,int t,int flow) {
    if(u == t)
        return flow;
    int remain = flow;
    for(list<int>::iterator it = L[u].begin();it != L[u].end() && remain;it++) {
        int v = edge[*it].v;
        if(dist[v] == dist[u] + 1 && edge[*it].w) {
            int k = dfs(v,t,min(remain,edge[*it].w));
            if(!k)
                dist[v] = 0;
            edge[*it].w -= k;
            edge[(*it) ^ 1].w += k;
            remain -= k;
        }
    }
    return flow - remain;
}
int Dinic(int u,int v) {
    int ans = 0;
    while(bfs(u,v))
        ans += dfs(u,v,INF);
    return ans;
}

void Do() {
    //读入并建图
    init();
    cin >> n >> m;
    for(int i = 0;i < m;i++) {
        cin >> road[i].u >> road[i].v >> road[i].w;
        add(road[i].u,road[i].v,1);
        add(road[i].v,road[i].u,1);
    }

    //BFS计算所有点到源点的距离
    while(!Q.empty())
        Q.pop();
    for(int i = 1;i <= n;i++)
        dist[i] = INF;
    memset(vis,false,sizeof(vis));

    Q.push(1);
    dist[1] = 0;
    vis[1] = true;

    while(!Q.empty()) {
        int u = Q.front();
        Q.pop();
        for(list<int>::iterator it = L[u].begin();it != L[u].end();it++) {
            int v = edge[*it].v;
            if(!vis[v]) {
                vis[v] = true;
                dist[v] = dist[u] + 1;
                Q.push(v);
            }
        }
    }

    //重新建图,新图中只有最短路和死路
    init();
    for(int i = 0;i < m;i++) {
        int mx,mi;
        if(dist[road[i].u] > dist[road[i].v]) {
            mx = road[i].u;
            mi = road[i].v;
        } else {
            mi = road[i].u;
            mx = road[i].v;
        }

        //较远点比较近点恰好远1个单位
        if(dist[mx] - dist[mi] == 1) {
            add(mi,mx,road[i].w);
            add(mx,mi,0);
        }
    }

    //Dinic模板求最大流(最小割)
    cout << Dinic(1,n) << endl;
}

int main() {
    cin.tie(0);
    cin.sync_with_stdio(false);

    int T;
    cin >> T;

    while(T--)
        Do();

    return 0;
}