Dinic_maxflow.cpp

/*
    Algorithm : Dinic's Algorithm for Maximum Flow
    Complexity : V^2*E
    Problem : LightOJ - 1153
*/

#include <bits/stdc++.h>

using namespace std;

#define INF 2000000000
const int MAX_E=20005;
const int MAX_V=505;
int ver[MAX_E],cap[MAX_E],nx[MAX_E],last[MAX_V],ds[MAX_V],st[MAX_V],now[MAX_V],edge_count,S,T;

inline void reset()
{
    memset(nx,-1,sizeof(nx));
    memset(last,-1,sizeof(last));
    edge_count=0;
}

inline void addedge(const int v,const int w,const int capacity,const int reverse_capacity)
{
    ver[edge_count]=w; cap[edge_count]=capacity; nx[edge_count]=last[v]; last[v]=edge_count++;
    ver[edge_count]=v; cap[edge_count]=reverse_capacity; nx[edge_count]=last[w]; last[w]=edge_count++;
}

inline bool bfs()
{
    memset(ds,-1,sizeof(ds));
    int a,b;
    a=b=0;
    st[0]=T;
    ds[T]=0;
    while (a<=b)
    {
        int v=st[a++];
        for (int w=last[v];w>=0;w=nx[w])
        {
            if (cap[w^1]>0 && ds[ver[w]]==-1)
            {
                st[++b]=ver[w];
                ds[ver[w]]=ds[v]+1;
            }
        }
    }
    return ds[S]>=0;
}

int dfs(int v,int cur)
{
    if (v==T) return cur;
    for (int &w=now[v];w>=0;w=nx[w])
    {
        if (cap[w]>0 && ds[ver[w]]==ds[v]-1)
        {
            int d=dfs(ver[w],min(cur,cap[w]));
            if (d)
            {
                cap[w]-=d;
                cap[w^1]+=d;
                return d;
            }
        }
    }
    return 0;
}

inline int dinic()
{
    int res=0;
    while (bfs())
    {
        for (int i=0;i<MAX_V;i++) now[i]=last[i];
        while (1)
        {
            int tf=dfs(S,INF);
            res+=tf;
            if (!tf) break;
        }
    }
    return res;
}

int main()
{
    //freopen("input.txt","r",stdin);
    int cases;
    scanf("%d", &cases);
    int caseno = 0;
    while(cases--){
        reset();
        int node, edge;
        scanf("%d", &node);
        scanf("%d %d %d", &S, &T, &edge);
        for(int i=0; i<edge; i++){
            int u, v, c;
            scanf("%d %d %d", &u, &v, &c);
            addedge(u, v, c, 0);
            addedge(v, u, c, 0); // For this problem, Bidirectional Graph
        }
        printf("Case %d: %d\n", ++caseno, dinic());
    }
}

/*
    4
    4
    1 4 2
    4 1 232
    1 4 490
    3
    1 2 2
    3 2 188
    2 1 100
    7
    2 6 6
    3 6 127
    3 4 515
    4 6 114
    2 3 123
    7 1 866
    4 7 588
    3
    3 1 7
    1 3 763
    1 2 883
    3 1 383
    1 2 641
    2 1 411
    2 3 229
    2 1 345

    Case 1: 722
    Case 2: 100
    Case 3: 123
    Case 4: 1375
*/