446

# 题目

## 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.

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

4

# 题解

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

# 代码

/*
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;
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++) {
}

//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;
} else {
}

//较远点比较近点恰好远1个单位
if(dist[mx] - dist[mi] == 1) {
}
}

//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;
}

• 点击查看/关闭被识别为广告的评论