[最小割+dijkstra]中科大ACM大みそかチャレンジA

大まかな題意:n個のノード、m個のエッジからなる無方向図を与え、各エッジにはそれぞれの長さと費用値cがあり、この無方向エッジに必要な費用を削除することを意味する.2つの点sとtを与えて、今いくつかの辺を削除してsからtまでの最短路を増加させて、費用が最も少ないことを求めます.
 
大まかな考え方:
まず、1つのエッジ(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
",cas,0);
            continue;
        }
        buildmap(s,t,n);
        printf("Case %d: %d
",cas,dinic(s,t));
    }
    return 0;
}