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