题解：最大流问题（Dinic算法）

题目分析

本题是典型的最大流问题，要求计算水从水塘（节点 ( 1 )）到小溪（节点 ( M )）的最大流量。每条沟渠有特定的水流方向和容量，通过构建网络流模型，利用 Dinic 算法求解最大流。

算法思路

Dinic 算法基于分层图，通过 BFS 构建分层图，然后在分层图上用 DFS 寻找增广路。具体步骤如下：

1. BFS 构建分层图：用 BFS 遍历图，给每个节点标记到源点的距离（层数），若无法到达汇点则结束。
2. DFS 寻找增广路：在分层图上，从源点开始，沿着层数 ( +1 ) 的边寻找增广路，直到汇点。找到后更新残留网络，记录增广流量。
3. 重复过程：不断重复 BFS 和 DFS，直到 BFS 无法到达汇点，此时的总流量即为最大流。

代码实现

1. 输入处理：读取测试用例，构建邻接矩阵 tab 存储边的容量。
2. BFS 函数：
   • 初始化 dis 数组为 ( -1 )，dis[1] = 0，队列初始化。
   • 遍历队列，更新每个可达节点的层数 dis[i]。
   • 若 dis[M] <= 0，返回 ( 0 ) 表示无路径；否则返回 ( 1 )。
3. find 函数（DFS 增广）：
   • 若到达汇点 ( M )，返回当前路径最小容量 low。
   • 遍历邻接节点，若满足分层图条件且能找到增广路（a != 0），更新残留网络，返回增广流量。
4. 主函数：
   • 循环读取测试用例，初始化邻接矩阵。
   • 调用 BFS 和 find 函数，累加增广流量 ANS，直到无法增广。
   • 输出最大流量 ANS。

代码解释

• tab 数组：邻接矩阵，存储边的容量和残留容量。
• dis 数组：记录节点到源点的层数（距离）。
• q 队列：BFS 使用的队列。
• BFS 函数构建分层图，find 函数在分层图上增广。
• 主函数中，每次 BFS 后多次 find 增广，直到无增广路，最终 ANS 即为最大流。

通过上述 Dinic 算法的实现，高效地求解了最大流问题，满足题目要求。例如输入数据 ( 1 )，经过计算最终输出最大流量 ( 50 )，与题目输出一致。

#include <cstdio> 
#include <cstring> 
#include <cstdlib> 
#include <iostream> 
#define min(x,y) ((x<y)?(x):(y)) 
using namespace std; 
const int MAX=0x5fffffff;

int tab[250][250];  // 邻接矩阵  
int dis[250];      // 距源点距离,分层图  
int q[2000],h,r;   // BFS队列 ,首,尾  
int N,M,ANS;       // N:点数;M,边数  

int BFS() {
    int i,j; 
    memset(dis,0xff,sizeof(dis));  // 以-1填充  
    dis[1]=0; 
    h=0; r=1; 
    q[1]=1; 
    while (h<r) {
        j=q[++h]; 
        for (i=1;i<=N;i++) 
            if (dis[i]<0 && tab[j][i]>0) {
                dis[i]=dis[j]+1;  
                q[++r]=i; 
            }
    }
    if (dis[N]>0) 
        return 1; 
    else 
        return 0;  // 汇点的DIS小于零,表明BFS不到汇点  
} 

// Find代表一次增广,函数返回本次增广的流量,返回0表示无法增广  
int find(int x,int low) {  // Low是源点到现在最窄的(剩余流量最小)的边的剩余流量
    int i,a=0; 
    if (x==N) return low;  // 是汇点  

    for (i=1;i<=N;i++) 
        if (tab[x][i] >0  // 联通  
            && dis[i]==dis[x]+1  // 是分层图的下一层  
            && (a=find(i,min(low,tab[x][i]))))  // 能到汇点(a <> 0)  
        { 
            tab[x][i]-=a; 
            tab[i][x]+=a; 
            return a; 
        } 
    return 0; 
} 

int main() {
    //freopen("ditch.in" ,"r",stdin );
    //freopen("ditch.out","w",stdout);
    int i,f,t,flow,tans;  // 删除未使用的变量j
    while (scanf("%d%d",&M,&N)!=EOF) {
        memset(tab,0,sizeof(tab)); 
        for (i=1;i<=M;i++) {
            scanf("%d%d%d",&f,&t,&flow); 
            tab[f][t]+=flow; 
        }
        ANS=0; 
        while (BFS()) {  // 要不停地建立分层图,如果BFS不到汇点才结束  
            while((tans=find(1,0x7fffffff)))  // 加上括号消除警告
                ANS+=tans;  // 一次BFS要不停地找增广路,直到找不到为止  
        }
        printf("%d\n",ANS); 
    }
    //system("pause"); 
}