[最小割+dijkstra]中科大ACM除夕挑战赛A
大致题意：
? ? ?给出一个由n个节点，m条边组成的无向图，每条边都有各自的长度和一个花费值c，意味着删去这条无向边需要的花费。给出两个点s和t，现在要删去一些边使得s到t的最短路增加，求花费最少是多少。
?
大致思路：
? ? 首先，对于一条边(u,v)，如果s—>v== s—>u +u—>v我们就可以认为这条边是s到t的最短路上面的一条边。用dijkstra先求出s到所有点的最短距离，然后枚举每条边用上面的方法判定这条边是否在最短路上。如果(u,v)是属于某个最短路的一条边，则在网络图中加上u->v，容量设为删去这条边的花费。接下来对图中的s点到t点求一遍最小割，得到的就是答案。
?
#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;const int nMax=1500;const int mMax=200000;class node{ public: int c,u,v,next;};node edge[mMax];int ne, head[nMax],n;int cur[nMax], ps[nMax], dep[nMax];const int inf=1<<29;void addedge(int u, int v,int c){ ////dinic的加边方法 // cout<<u<<" add "<<v<<" "<<c<<endl; edge[ne].u = u; edge[ne].v = v; edge[ne].c = c; edge[ne].next = head[u]; head[u] = ne ++; edge[ne].u = v; edge[ne].v = u; edge[ne].c = 0; edge[ne].next = head[v]; head[v] = ne ++;}int dinic(int s, int t){ // 网络流dinic算法。 int tr, res = 0; int i, j, k, f, r, top; while(1){ memset(dep, -1, sizeof(dep)); for(f = dep[ps[0]=s] = 0, r = 1; f != r;) for(i = ps[f ++], j = head[i]; j; j = edge[j].next) if(edge[j].c && dep[k=edge[j].v] == -1){ dep[k] = dep[i] + 1; ps[r ++] = k; if(k == t){ f = r; break; } } if(dep[t] == -1) break; memcpy(cur, head, sizeof(cur)); i = s, top = 0; while(1){ if(i == t){ for(tr =inf, k = 0; k < top; k ++) if(edge[ps[k]].c < tr) tr = edge[ps[f=k]].c; for(k = 0; k < top; k ++) { edge[ps[k]].c -= tr; edge[ps[k]^1].c += tr; } i = edge[ps[top=f]].u; res += tr; } for(j = cur[i]; cur[i]; j = cur[i] =edge[cur[i]].next){ if(edge[j].c && dep[i]+1 == dep[edge[j].v]) break; } if(cur[i]){ ps[top ++] = cur[i]; i = edge[cur[i]].v; } else{ if(top == 0) break; dep[i] = -1; i = edge[ps[-- top]].u; } } } return res;}int map[nMax][nMax],co[nMax][nMax],dis[nMax];bool vis[nMax];void dijkstra(int from){ for(int i=0;i<=n;i++)dis[i]=inf; memset(vis,false,sizeof(vis)); vis[from]=true; dis[from]=0; int mine; int now=from; for(int i=1;i<n;i++){ for(int k=1;k<=n;k++) if( map[now][k]!=inf&&dis[now]!=inf&&map[now][k]+dis[now]<dis[k]) dis[k] = dis[now] + map[now][k]; mine=inf; for(int k=1;k<=n;k++) if(mine>dis[k]&&!vis[k]) mine=dis[now=k]; vis[now]=true; } // for(int i=1;i<=n;i++)cout<<dis[i]<<" ";cout<<endl;}void buildmap(int s,int t,int N){ int i,j; for(i=1;i<=N;i++){ if(dis[i]==inf)continue; for(j=1;j<=N;j++){ if(i==j)continue; if(dis[j]==dis[i]+map[i][j])addedge(i,j,co[i][j]); } }}int main(){ int i,j,m,a,b,c,s,t,u,v,cas=0; while(scanf("%d%d",&n,&m)!=EOF&&(n||m)){ cas++; ne=2; memset(head,0,sizeof(head)); scanf("%d%d",&s,&t); for(i=1;i<=n;i++){ for(j=0;j<=n;j++){ map[i][j]=inf; }map[i][i]=0; } while(m--){ scanf("%d%d",&u,&v); scanf("%d%d",&a,&b); if(a>map[u][v])continue; if(a==map[u][v]){ co[u][v]+=b; co[v][u]+=b; continue; } map[u][v]=a; co[v][u]=co[u][v]=b; map[v][u]=map[u][v]; } dijkstra(s); if(dis[t]==inf){ printf("Case %d: %d\n",cas,0); continue; } buildmap(s,t,n); printf("Case %d: %d\n",cas,dinic(s,t)); } return 0;}?