HDU-3549Flow Problem 最大流模板题

这里是Ford-Fulkerson写的最大流模板

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define lson (l , mid , rt << 1)
#define rson (mid + 1 , r , rt << 1 | 1)
#define debug(x) cerr << #x << " = " << x << "\n";
#define pb push_back
#define pq priority_queue

#define Pll pair
#define Pii pair

#define fi first
#define se second

#define OKC ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef long long ll;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;

/*-----------------show time----------------*/
const int maxn = 1e3+9;
struct node {
    int to,cap,rev;
};

vectormp[maxn];
bool used[maxn];

void add_edge(int from,int to,int cap)
{
    mp[from].pb((node){to,cap,(int)mp[to].size()});
    mp[to].pb((node){from,0,(int)mp[from].size()-1});   
}

int dfs(int v,int t,int f)
{
    if(v==t)return f;
    used[v] = true;
    for(int i=0; i0)
        {
            int d = dfs(e.to,t,min(f,e.cap));
            if(d>0)
            {
                e.cap -= d;
                mp[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

int max_flow(int s,int t)
{
    int flow = 0;
    for(;;)
    {
        memset(used,0,sizeof(used));
        int f = dfs(s,t,inf);
        if(f==0)return flow;
        flow += f;
    }
}
int main(){
    int t,n,m;
    scanf("%d", &t);
    for(int T=1; T<=t;T++)
    {
        scanf("%d%d", &n, &m);
        for(int i=0;i<=n;i++)mp[i].clear();
        for(int i=1; i<=m; i++)
        {
            int u,v,c;
            scanf("%d%d%d", &u, &v, &c);
            add_edge(u,v,c);
        }
        printf("Case %d: %d\n",T,max_flow(1,n));
    }

    return 0;
}

HDU 3549

相关阅读:
SpringBoot-黑马程序员-学习笔记（二）
LeetCode每日一题(2216. Minimum Deletions to Make Array Beautiful)
Hive的分区和分桶
JAVA计算机毕业设计在线辅导答疑系统Mybatis+源码+数据库+lw文档+系统+调试部署
14.信号量的代码实现
mrctf2020_shellcode_revenge
.Net FramWork 和Net Core3.1配置Log4.net
（最优化理论与方法）第三章优化建模-第一节：优化建模和常见建模技术
陈瑞瑞潘童童程乐黄明深哈夫曼编码与信道编码
指令系统（考研笔记）

原文地址：https://blog.csdn.net/weixin_67271870/article/details/127857235