【HDU - 5889】Barricade（最短路+网络流，最小割）

题干：

The empire is under attack again. The general of empire is planning to defend his castle. The land can be seen as NN towns and MM roads, and each road has the same length and connects two towns. The town numbered 11 is where general's castle is located, and the town numbered NN 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 ii-th road requires wiwi 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 tt, then tt test cases follow.
For each test case, in the first line there are two integers N(N≤1000)N(N≤1000) and M(M≤10000)M(M≤10000).
The ii-the line of the next MM lines describes the ii-th edge with three integers u,vu,vand ww where 0≤w≤10000≤w≤1000 denoting an edge between uu and vv of barricade cost ww.

Output

For each test cases, output the minimum wood cost.

Sample Input

Sample Output

题目大意：

我在1号点，敌人在n号点，敌人会走n到1的最短路径进攻你了，现在你需要在路径上放置障碍，但是每条边上放置障碍有一个花费，求能阻挡所有敌人放置最少花费的障碍。

解题报告：

因为边的长度都是1，所以直接bfs求最短路，然后建出最短路子图，然后求最小割就行了。题目思路很清晰，算是一道比较简单的网络流。

AC代码：

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
const int MAX = 2e5 +5;
int n;
int tot,TOT;
struct Edge {
	int to,ne,w;
} e[100005 * 2];
struct EE {
	int fr,to,ne,w;
}E[100005 +5];
int head[10005],HEAD[10005];
int st,ed;
int dis[10050],q[10005];//一共多少个点跑bfs，dis数组和q数组就开多大。 
void add(int u,int v,int w) {
	e[++tot].to=v;
	e[tot].w=w;
	e[tot].ne=head[u];
	head[u]=tot;
}
void addE(int u,int v,int w) {
	E[++TOT].to=v;
	E[TOT].fr = u;
	E[TOT].w=w;
	E[TOT].ne=HEAD[u];
	HEAD[u]=TOT;
}
bool bfs(int st,int ed) {
	memset(dis,-1,sizeof(dis));
	int front=0,tail=0;
	q[tail++]=st;
	dis[st]=0;
	while(front<tail) {
		int cur = q[front];
		if(cur == ed) return 1;
		front++;
		for(int i = head[cur]; i!=-1; i = e[i].ne) {
			if(e[i].w&&dis[e[i].to]<0) {
				q[tail++]=e[i].to;
				dis[e[i].to]=dis[cur]+1;
			}
		}
	}
	if(dis[ed]==-1) return 0;
	return 1;
}
int dfs(int cur,int limit) {//limit为源点到这个点的路径上的最小边权 
	if(limit==0||cur==ed) return limit;
	int w,flow=0;
	for(int i = head[cur]; i!=-1; i = e[i].ne) {		
		if(e[i].w&&dis[e[i].to]==dis[cur]+1) {
			w=dfs(e[i].to,min(limit,e[i].w));
			e[i].w-=w;
			e[i^1].w+=w;
			flow+=w;
			limit-=w;
			if(limit==0) break;
		}
	}
	if(!flow) dis[cur]=-1;
	return flow;
}
int dinic() {
	int ans = 0;
	while(bfs(st,ed)) 
		ans+=dfs(st,0x7fffffff);
	return ans;
}
int DIS[MAX];
int vis[MAX];
struct Point {
	int pos,step;
	Point(){}
	Point(int pos,int step):pos(pos),step(step){}
}; 
int flag[MAX];
void bfs() {
	for(int i = 1; i<=n; i++) vis[i] = 0,DIS[i] = -1;
	queue<Point> q;
	q.push(Point(1,0));
	vis[1] = 1;
	while(!q.empty()) {
		Point cur = q.front();q.pop();
//		if(vis[cur.pos] == 1) continue;
		for(int i = HEAD[cur.pos]; ~i; i = E[i].ne) {
			int v = E[i].to;
			if(vis[v] == 1) {
				if(cur.step+1 == DIS[v]) {
					flag[i] = 1;
				}
			}
			else {
				DIS[v] = cur.step+1;
				vis[v] = 1;
				flag[i] = 1;
				q.push(Point(v,DIS[v]));
			}
		}
	}
}
int main() 
{
	int t,m;
	cin>>t;
	while(t--) {
		scanf("%d%d",&n,&m);
		//init
		tot=1,TOT=0;
		for(int i = 0; i<=2*m; i++) flag[i] = 0;
		for(int i = 1; i<=n; i++) head[i] = HEAD[i] = -1;		
		for(int u,v,w,i = 1; i<=m; i++) {
			scanf("%d%d%d",&u,&v,&w);
			addE(u,v,w);addE(v,u,w);
		} 
		bfs();
		for(int i = 1; i<=TOT; i++) {
			if(flag[i] == 1) {
				add(E[i].fr,E[i].to,E[i].w);
				add(E[i].to,E[i].fr,0);
			}
		}
		st=1,ed=n;
		printf("%d\n",dinic());	
	}
	return 0;
}
/*
3
4 4
1 2 1
2 4 2
3 1 3
4 3 4

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

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

*/