Flow Problem

Myth丶恋晨 2022-01-05 15:27 328阅读 0赞

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

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

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

网络流 纯的sap算法。（用递归）

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<iostream>
      2 #include<string>
      3 #include<cstring>
      4 #include<cmath>
      5 #include<algorithm>
      6 #include<cstdio>
      7 #include<queue>
      8 #include<vector>
      9 #include<stack>
     10 #define  inf   0x3fffffff
     11 using namespace std;
     12 int lvl[2020],gap[2020],idx,source,sink,n,m,head[2020];
     13 int T;
     14 int min(int a,int b)
     15  {
     16      return a>b?b:a;
     17  }
     18 struct nodedge
     19  {
     20      int next;
     21      int to;
     22      int cap;
     23  }e[2020];
     24  int i,j,k,num;
     25  void  add(int a,int b,int c)//加边，正向&&反向
     26   {
     27       e[num].cap=c;
     28       e[num].to=b;
     29       e[num].next=head[a];
     30       head[a]=num;
     31       num++;
     32       e[num].cap=0;
     33       e[num].to=a;
     34       e[num].next=head[b];
     35       head[b]=num;
     36       num++;
     37   }
     38   int dfs(int src,int aug)
     39    {
     40        if(src==sink)//到汇点返回
     41         return aug;
     42        int tf=0,sf,mlvl=n-1;
     43        for(int it=head[src];it!=-1;it=e[it].next)//链式前向星
     44         {
     45             if(e[it].cap>0)//边仍然有容量
     46              {
     47                  if(lvl[src]==lvl[e[it].to]+1)//判断是否为最短边
     48                    {
     49                        sf=dfs(e[it].to,min(aug-tf,e[it].cap));//向下递归，到汇点时的值
     50                         e[it].cap-=sf;
     51                         e[it^1].cap+=sf;//反向加
     52                         tf+=sf;//与流入节点的最大流量比较
     53 
     54                     if(lvl[source]>=n)//如果节点的层数大于最大返回（注意是反向的）
     55                      return tf;
     56                     if(tf==aug)//等于最大流量时返回
     57                      break;
     58                     }
     59                   mlvl=min(mlvl,lvl[e[it].to]);//求最近边
     60              }
     61         }
     62         if(tf==0)//出现断层时
     63         {
     64          --gap[lvl[src]];
     65          if(gap[lvl[src]]==0)
     66           lvl[source]=n;
     67           else
     68            {
     69                lvl[src]=mlvl+1;
     70                 gap[lvl[src]]++;
     71            }
     72 
     73         }
     74     return tf;
     75    }
     76   int sap()
     77   {
     78       int ans=0;
     79       gap[0]=n;
     80       while(lvl[source]<n)
     81        ans+=dfs(source,inf);
     82       return ans;
     83   }
     84   int main()
     85   {
     86     cin>>T;
     87     int st,en,c,ps=0;
     88     while(T--)
     89      {
     90          ps++;
     91          memset(lvl,0,sizeof(lvl));
     92          memset(gap,0,sizeof(gap));
     93          memset(head,-1,sizeof(head));
     94          cin>>n>>m;
     95          num=0;
     96          for(i=1;i<=m;i++)
     97           {
     98               cin>>st>>en>>c;
     99               add(st,en,c);
    100           }
    101         sink=n;source=1;
    102         cout<<"Case "<<ps<<": "<<sap()<<endl;
    103      }
    104   }

奋进

转载于:https://www.cnblogs.com/sdau--codeants/p/3276303.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211228/ff0f82ab29534e1ea51529ea9311b2a2.png