题目链接：HDU 5294 Tricks Device

题意：n个点，m条边。而且一个人从1走到n仅仅会走1到n的最短路径。问至少破坏几条边使原图的最短路不存在。最多破坏几条边使原图的最短路劲仍存在

思路：

1.跑一遍最短路。记录下全部最短路径，将这些最短路径的边以（0,1）（流量，容量）加到网络流中，跑一遍最大流

2.记录下的全部最短路径，再加到新的最短路的图中，边权为1，跑一遍最短路。m-最短路 就是答案

注意：有重边的情况

比方：

2 3

1 2 1

1 2 1

1 2 1

ans: 3 2

AC代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <queue>

#include <set>

using namespace std;

const int MAXN=2010;

const int MAXM=60010;

#define typec int

const typec INF=0x3f3f3f3f;//防止后面溢出，这个不能太大

struct Edge {

	int to,next,cap,flow;

} edge[MAXM*4]; //注意是MAXM

int tol;

int head[MAXN];

int gap[MAXN],dep[MAXN],cur[MAXN];

void add(int u,int v,int w,int rw = 0) {

	edge[tol].to = v;

	edge[tol].cap = w;

	edge[tol].flow = 0;

	edge[tol].next = head[u];

	head[u] = tol++;

	edge[tol].to = u;

	edge[tol].cap = rw;

	edge[tol].flow = 0;

	edge[tol].next = head[v];

	head[v] = tol++;

}

int Q[MAXN];

void BFS(int start,int end) {

	memset(dep,-1,sizeof(dep));

	memset(gap,0,sizeof(gap));

	gap[0] = 1;

	int front = 0, rear = 0;

	dep[end] = 0;

	Q[rear++] = end;

	while(front != rear) {

		int u = Q[front++];

		for(int i = head[u]; i != -1; i = edge[i].next) {

			int v = edge[i].to;

			if(dep[v] != -1)continue;

			Q[rear++] = v;

			dep[v] = dep[u] + 1;

			gap[dep[v]]++;

		}

	}

}

int S[MAXN];

int sap(int start,int end,int N) {

	BFS(start,end);

	memcpy(cur,head,sizeof(head));

	int top = 0;

	int u = start;

	int ans = 0;

	while(dep[start] < N) {

		if(u == end) {

			int Min = INF;

			int inser;

			for(int i = 0; i < top; i++)

				if(Min > edge[S[i]].cap - edge[S[i]].flow) {

					Min = edge[S[i]].cap - edge[S[i]].flow;

					inser = i;

				}

				for(int i = 0; i < top; i++) {

					edge[S[i]].flow += Min;

					edge[S[i]^1].flow -= Min;

				}

				ans += Min;

				top = inser;

				u = edge[S[top]^1].to;

				continue;

		}

		bool flag = false;

		int v;

		for(int i = cur[u]; i != -1; i = edge[i].next) {

			v = edge[i].to;

			if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u]) {

				flag = true;

				cur[u] = i;

				break;

			}

		}

		if(flag) {

			S[top++] = cur[u];

			u = v;

			continue;

		}

		int Min = N;

		for(int i = head[u]; i != -1; i = edge[i].next)

			if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min) {

				Min = dep[edge[i].to];

				cur[u] = i;

			}

			gap[dep[u]]--;

			if(!gap[dep[u]])return ans;

			dep[u] = Min + 1;

			gap[dep[u]]++;

			if(u != start)u = edge[S[--top]^1].to;

	}

	return ans;

}

void init() {

	tol = 0;

	memset(head,-1,sizeof(head));

}

//-------------------------------------------------

struct Edge2 {

	int v;

	int cost;

	Edge2(int _v=0,int _cost=0):v(_v),cost(_cost){}

};

vector<Edge2>E[MAXN],E2[MAXN];

void addedge(int u,int v,int w) {

	E[u].push_back(Edge2(v,w));

}

bool vis[MAXN];//在队列标志

int cnt[MAXN];//每一个点的入队列次数

int dist[MAXN];

bool SPFA(int start,int n) {

	memset(vis,false,sizeof(vis));

	for(int i=1;i<=n;i++)

		dist[i]=INF;

	vis[start]=true;

	dist[start]=0;

	queue<int>que;

	while(!que.empty())que.pop();

	que.push(start);

	memset(cnt,0,sizeof(cnt));

	cnt[start]=1;

	while(!que.empty())	{

		int u=que.front();

		que.pop();

		vis[u]=false;

		for(int i=0;i<E[u].size();i++){

			int v=E[u][i].v;

			if(dist[v]>dist[u]+E[u][i].cost){

				dist[v]=dist[u]+E[u][i].cost;

				if(!vis[v]){

					vis[v]=true;

					que.push(v);

					if(++cnt[v]>n) return false;

					//cnt[i]为入队列次数，用来判定是否存在负环回路

				}

			}

		}

	}

	return true;

}

set<int> s;

int main() {

	int i,j,m,n;

	int a,b,c;

	while(scanf("%d %d",&n,&m)!=EOF) {

		init();

		s.clear();

		for(i=1;i<=n;i++) E[i].clear();

		for(i=0; i<m; i++) {

			scanf("%d %d %d",&a,&b,&c);

			addedge(a,b,c);

			addedge(b,a,c);

		}

		int ok=SPFA(1,n);

		for(i=1;i<=n;i++){

			E2[i]=E[i];

			E[i].clear();

		}

		for(i=1; i<=n; i++) {

			int sz=E2[i].size();

			for(j=0; j<sz; j++) {

				int u=i;

				int v=E2[i][j].v;

				//得到最短路的边

				if(dist[u]+E2[i][j].cost==dist[v]) {

					add(u,v,1);

					s.insert(u),s.insert(v);

					addedge(u,v,1);

				}

			}

		}

		int ans=sap(1,n,(int)s.size());

		ok=SPFA(1,n);

		printf("%d %d\n",ans,m-dist[n]);

	}

	return 0;

}

/*

2 3

1 2 1

1 2 1

1 2 1

2 5

1 2 2

1 2 2

1 2 1

1 2 1

1 2 1

*/