题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6582
题意：有n个点,m条单向带权边，起点为1，终点为n，如果开始没有最短路输出0,现在想堵住一些路，使堵之后的最短路值变大，或不存在。堵路的花费就是边的权值，问最小花费。
思路：找到最短路核心边，再重新建边，跑一遍最小割即可。找最短路核心边要正向建边找每点到起点的距离（假设为d[i]），再反向建边找每点到终点的距离(假设为d2[i])，如果一条边起点为u,终点为v，边权为w,若d[u]+d2[v]+w==d[n]则这是一条最短路核心边。
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; typedef long long ll; const int maxn=20100; const int maxm=20100; const ll inf=1e18; struct node{ int u,v,nxt; ll w; }e[2*maxm],e2[2*maxm],e3[2*maxm]; int h[maxn],h2[maxn],h3[maxn],depth[maxn]; ll d[maxn],d2[maxn]; bool vis[maxn]; int n,m,st,ed,cnt,cnt2,cnt3; void init() { memset(h,-1,sizeof(h)); memset(h2,-1,sizeof(h2)); memset(h3,-1,sizeof(h3)); for(int i=0;i<=n;i++) d[i]=d2[i]=inf; cnt=cnt2=cnt3=0; } void add(int u,int v,ll w)//正向建边 { e[cnt].u=u,e[cnt].v=v,e[cnt].w=w; e[cnt].nxt=h[u];h[u]=cnt++; } void add2(int u,int v,ll w)//反向建边 { e2[cnt2].u=u,e2[cnt2].v=v,e2[cnt2].w=w; e2[cnt2].nxt=h2[u],h2[u]=cnt2++; } void add3(int u,int v,ll w)//重新建边 { e3[cnt3].u=u,e3[cnt3].v=v,e3[cnt3].w=w; e3[cnt3].nxt=h3[u],h3[u]=cnt3++; } bool spfa()//求每点到1的最短距离 { queue<int> q; memset(vis,0,sizeof(vis)); d[st]=0; vis[st]=1; q.push(st); while(!q.empty()) { int u=q.front();q.pop(); vis[u]=0; for(int i=h[u];i!=-1;i=e[i].nxt) { int v=e[i].v; ll w=e[i].w; if(d[v]>d[u]+w) { d[v]=d[u]+w; if(!vis[v]) { vis[v]=1; q.push(v); } } } } return d[n]==inf; } void re_spfa()//求每点到n的最短距离 { queue<int> q; memset(vis,0,sizeof(vis)); d2[ed]=0; vis[ed]=1; q.push(ed); while(!q.empty()) { int u=q.front();q.pop(); vis[u]=0; for(int i=h2[u];i!=-1;i=e2[i].nxt) { int v=e2[i].v; ll w=e2[i].w; if(d2[v]>d2[u]+w) { d2[v]=d2[u]+w; if(!vis[v]) { vis[v]=1; q.push(v); } } } } } void create_map()//重新建边 { for(int i=0;i<cnt;i++) { int u=e[i].u; int v=e[i].v; ll w=e[i].w; if((d[u]+d2[v]+w==d[ed])&&(d[u]<inf&&d2[v]<inf)) {//最短路核心边 add3(u,v,w); add3(v,u,0); } } } bool bfs(){//dinic分层 queue<int> que; memset(depth,0,sizeof(depth)); que.push(st); depth[st]=1; while(!que.empty()){ int u=que.front(); que.pop(); if(u==ed) return true; for(int i=h3[u];i!=-1;i=e3[i].nxt){ int v=e3[i].v; ll w=e3[i].w; if(!depth[v]&&w){ depth[v]=depth[u]+1; que.push(v); } } } return false; } ll dfs(int u,ll dis) { if(u==ed) return dis; ll res=0; for(int i=h3[u];i!=-1;i=e3[i].nxt) { int v=e3[i].v; ll w=e3[i].w; if((depth[v]==depth[u]+1)&&w) { ll di=dfs(v,min(w,dis-res)); e3[i].w-=di; e3[i^1].w+=di; res+=di; if(res==dis) return dis; } } return res; } void dinic()//dinic求最小割 { ll ans=0; while(bfs()) { ans+=dfs(st,inf); } printf("%lld ",ans); } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); st=1,ed=n; init(); for(int i=0;i<m;i++) { int u,v;ll w; scanf("%d%d%lld",&u,&v,&w); add(u,v,w); add2(v,u,w); } if(spfa())//特判，没有最短路 printf("0 "); else { re_spfa(); create_map(); dinic(); } } return 0; }