首页 > 其他分享 >AcWing 进阶课知识点模板梳理

AcWing 进阶课知识点模板梳理

时间:2024-11-17 09:40:05浏览次数:1  
标签:知识点 进阶 idx int ne long st AcWing

EK 求最大流

点击查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1005, M = 20005,INF=1e8;
int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], pre[N];
bool st[N];
void add(int a,int b,int c){
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}

bool bfs(){
    int hh = 0, tt = 0;
    memset(st, 0, sizeof(st));
    q[0] = S, st[S] = 1,d[S] = INF;

    while(hh<=tt){
        int t = q[hh++];
        for (int i = h[t]; ~i;i=ne[i]){
            int ver = e[i];
            if(!st[ver]&&f[i]){
                st[ver] = 1;
                d[ver] = min(d[t], f[i]);
                pre[ver] = i;
                if(ver==T) return 1;
                 q[++tt] = ver;
            }
        }
    }
    return 0;
}
int EK(){
    int r = 0; 
    while(bfs()){
        r += d[T];
        for (int i = T; i != S;i=e[pre[i]^1])
            f[pre[i]] -= d[T], f[pre[i]^1] += d[T];
    }
    return r;
}
int main(){
    memset(h, -1, sizeof(h));
    cin >> n >> m >> S >> T;
    while(m--){
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        
    }
    cout << EK() << endl;
    return 0;
}

标签:知识点,进阶,idx,int,ne,long,st,AcWing
From: https://www.cnblogs.com/fanrunze/p/18550276

相关文章

  • HarmonyOS Next 网络加速进阶:优化策略与应用实践
    本文旨在深入探讨华为鸿蒙HarmonyOSNext系统(截止目前API12)的技术细节,基于实际开发实践进行总结。主要作为技术分享与交流载体,难免错漏,欢迎各位同仁提出宝贵意见和问题,以便共同进步。本文为原创内容,任何形式的转载必须注明出处及原作者。一、引言在上一篇博客中,我们已经初步......
  • SpringBoot进阶教程(八十三)Kaptcha
    Kaptcha是谷歌开源的一个可高度配置的比较老旧的实用验证码生成工具。它可以实现:(1)验证码的字体/大小颜色;(2)验证码内容的范围(数字,字母,中文汉字);(3)验证码图片的大小,边框,边框粗细,边框颜色(4)验证码的干扰线验证码的样式(鱼眼样式、3D、普通模糊)。v搭建架构添加maven引......
  • 【C++进阶实战】个人财务管理系统
    功能说明添加收入和支出记录:用户可以添加新的收入和支出记录。查看记录:用户可以查看所有的收入和支出记录。生成财务报告:用户可以生成总收入、总支出和剩余金额的报告。设定预算:用户可以设定每月的预算,并查看是否超出预算。文件存储:使用文件来存储记录,以便下次启动程序时仍然......
  • 【C++进阶实战】电子词典
    功能说明查询单词:用户可以输入一个单词,程序将显示该单词的释义。文件存储:使用文件来存储单词和释义,以便下次启动程序时仍然可用。用户界面:提供简单的命令行界面,让用户选择查询单词或退出程序。示例代码词库文件 dictionary.txt假设我们有一个词库文件dictionary.txt,内容......
  • 多线程进阶
    1.常见的锁策略如果你自己实现一把锁,你认为标准库给你提供的锁不够用,这个时候你就需要关注锁策略,其实synchronized已经非常好用了足够覆盖大多数的使用场景。这里的锁策略不是和java强相关的,其他语言但凡涉及到并发编程,设计到锁都可以谈到这样的锁策略。1.1乐观锁VS悲观锁......
  • #Java-面向对象进阶-1
    1.static静态属性static是Java中的一个修饰符,可用来修饰成员变量、成员方法a.静态变量被static修饰的成员变量称为静态变量静态变量被该类的所有成员共享调用方式:类名调用(推荐)对象名调用例:创建方法//在创建的类中:publicstaticStringname;调用:假设类为:Stud......
  • #Java-面向对象进阶-多态
    1.多态多态是面向对象三大特征之一,表示同类型的对象表现不同的形态表现形式:父类类型对象名称=子类对象;多态的前提:有继承关系有父类引用子类Fuf=newZi();有方法重写使用场景举例:当需要写一个注册的方法,但是这个方法要能实现不同对象的注册例如:老......
  • 进程的知识点
    进程的基本概念进程是操作系统中的一个执行单位,代表正在运行的程序实例。每个进程都有自己独立的内存空间和系统资源,独立于其他进程运行。进程的生命周期包括创建、就绪、运行、等待和终止等状态。进程的创建与管理在操作系统中,进程的创建和管理通常通过系统调用实现,如fork(......
  • 【模板进阶】std::is_union、std::is_class、std::integral_constant
    一、std::is_unionstd::is......
  • Android15音频进阶之input调节CarAudioService音量过程(九十四)
    简介:CSDN博客专家、《Android系统多媒体进阶实战》一书作者新书发布:《Android系统多媒体进阶实战》......