[最小割+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;}