题目链接：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 intconst typec INF=0x3f3f3f3f;//防止后面溢出，这个不能太大struct Edge {int to,next,cap,flow;} edge[MAXM*4]; //注意是MAXMint 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 31 2 11 2 11 2 12 51 2 21 2 21 2 11 2 11 2 1*/
版权声明：本文为博主原创文章，未经博主允许不得转载。
要知道，当你一直在担心错过了什么的时候，其实你已经错过了旅行的意义。
