Flow Problem

Description

Network flow is a well-known difficult problem for ACMers. Given a graph, your task is to find out the maximum flow for the weighted directed graph.

 

Input

The first line of input contains an integer T, denoting the number of test cases. 
For each test case, the first line contains two integers N and M, denoting the number of vertexes and edges in the graph. (2 <= N <= 15, 0 <= M <= 1000) 
Next M lines, each line contains three integers X, Y and C, there is an edge from X to Y and the capacity of it is C. (1 <= X, Y <= N, 1 <= C <= 1000)

 

Output

For each test cases, you should output the maximum flow from source 1 to sink N.

 

Sample Input

     
      2
3 2
1 2 1
2 3 1
3 3
1 2 1
2 3 1
1 3 1 
    
    

 

Sample Output

     
      Case 1: 1
Case 2: 2 
    
    

有向图 G = ( V, E )中

n有唯一的一个 源点S（入度为0：出发点）

n有唯一的一个 汇点 T（出度为0：结束点）

n图中每条弧 (u, v) 都有一非负 容量 c ( u, v )

满足上述条件的图G称为网络流图。

记为： G = ( V, E, C)

每条弧 ( u, v )上 给定一个实数f(u,v),满足：有

   0 <= f ( u, v ) <= c( u, v ),

则f(u,v)称为弧( u, v )上的流量。

如果有一组流量满足条件：

          源点s ：  流出量 = 整个网络的流量

          汇点t ：   流入量 =整个网络的流量

          中间点：总流入量 = 总流出量

    那么整个网络中的流量成为一个可行流。

类似的题目还有：

Drainage Ditches

acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=11549

#include <stdio.h>
#include <string.h>
#define MAXV   16
#define MAXN   500
#define inf    0x3fffffff
#define MIN(a,b) a>b?b:a
#define clr(p) memset(p,0,sizeof(p))

struct E
{
    int to;//edg[0].to=2 0->2是最大顶点边 
    int val;//最大顶点边权值 
    int next;//edg[0].next=1 0->1 是一条边  （顶点从大到小） 
};

E edg[MAXN];
int G[MAXV][MAXV],dis[MAXV],gap[MAXV],nodes;
int list[MAXV];//存顶点 到最大顶点边 
int source,sink,Vs;

void addedg(int from,int to,int val) //存路径 
{
    edg[nodes].to=to; edg[nodes].val=val; edg[nodes].next=list[from]; list[from]=nodes++;
    
    edg[nodes].to=from; edg[nodes].val=0; edg[nodes].next=list[to]; list[to]=nodes++;
}

int dfs(int src,int aug)//查找更新 
{
    if(src==sink)  return aug;

    int flow=0,min_d=Vs-1;
    for(int j=list[src]; j!=-1;j=edg[j].next)
       if(edg[j].val)
       {
           if(dis[src]==dis[edg[j].to]+1)
           {
               int t=dfs(edg[j].to,MIN(aug-flow,edg[j].val));

               edg[j].val-=t;
               edg[j^1].val+=t;
               flow+=t;

               if(dis[source]>=Vs) return flow;
               if(aug==flow)  break;
           }
           min_d=MIN(min_d,dis[edg[j].to]);
       }
       if(!flow)
       {
           if(!(--gap[dis[src]]))  dis[source]=Vs;  //gap[0]=4
           dis[src]=min_d+1;//节点 src相邻节点中有流量且标号最小的 标号+1 
           ++gap[dis[src]];   //gap[1]=1
       }
       return flow;
}

int maxflow_sap(int src,int ed)
{
    int ans(0);
    clr(dis); //dis是存标志的，dis[1]=2，1这个顶点标志位2
    clr(gap); // gap 是存标志的个数 gap[2]=3 标志为2的有3个                 
    gap[0]=Vs=ed;
    source=src; sink=ed;

    while(dis[source]<Vs)
        ans+=dfs(source,inf);
    return ans;
}
int main()
{
    int CS,c; 
    scanf("%d",&CS);
    for(c=1;c<=CS;++c)
    {
        clr(G);
        memset(list,-1,sizeof(list)); 
             nodes=0;
        int n,m; 
        scanf("%d %d",&n,&m);
        int i,j;
        for(i=1;i<=m;i++)
        {
            int x,y,c; scanf("%d %d %d",&x,&y,&c);
            G[x][y]+=c;//出现重边 
        }

        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
               if(G[i][j])
                   addedg(i,j,G[i][j]);
            }

            printf("Case %d: %d\n",c,maxflow_sap(1,n));
    }
    return 0;
}