当前位置: 首页 > news >正文

最大流笔记

概念

求两点间的路径中可在同一时间内通过的最大量

EK算法

通过bfs找通路,找到后回溯;

每确定一条边时,同时建立一天反方向的边以用来进行反悔操作(毕竟一次性找到正确方案的概率太低了)

code

#include<bits/stdc++.h>
#define ll long long
#define inl inline
#define re register
using namespace std;
inl int read() {int sum=0,f=1;char c=getchar();while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();}while(isdigit(c)) {sum=(sum<<3)+(sum<<1)+(c^48);c=getchar();}return sum*f;
}
const int N=210;
int dis[10000010],ans,head[N<<1],tot=1,n,m,f[210][210];
struct node{int to,w,nxt;
}e[10000010];
inl void add(int u,int v,int w) {e[++tot].to=v;e[tot].w=w;e[tot].nxt=head[u];head[u]=tot;e[++tot].to=u;e[tot].w=0;e[tot].nxt=head[v];head[v]=tot;
}
bool vis[210];
int pre[N];
inl bool bfs() {memset(vis,0,sizeof(vis));queue<int> q;dis[1]=100000000;vis[1]=1;q.push(1);while(!q.empty()) {int u=q.front();q.pop();for(re int i=head[u];i;i=e[i].nxt) {int v=e[i].to;if(vis[v]==1 || e[i].w==0) continue;dis[v]=min(dis[u],e[i].w) ;//cout<<dis[v]<<endl;pre[v]=i;q.push(v);vis[v]=1;if(v==n) return 1;}}return 0;
}
inl void update() {int u=n;while(u!=1) {int v=pre[u] ;e[v].w-=dis[n];e[v^1].w+=dis[n];u=e[v^1].to;}ans+=dis[n];
}
int main() {m=read(),n=read();for(re int i=1;i<=m;i++) {int u=read(),v=read(),w=read();if(!f[u][v]) {add(u,v,w);f[u][v]=tot;}else{e[f[u][v]-1].w+=w;}}while(bfs()) {//cout<<dis[n]<<endl;update();}cout<<ans<<endl;return 0;
}

Dinic算法

也是运用bfs将原图进行分层,但统计答案时使用dfs,,可大大降低时间复杂度

code

#include<bits/stdc++.h>
#define ll long long
#define re register
#define inl inline
using namespace std;
inl int read() {int sum=0,f=1;char c=getchar();while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();}while(isdigit(c)) {sum=(sum<<3)+(sum<<1)+(c^48);c=getchar();}return sum*f;
}
const int N=210;
int n,m,x,head[N<<1],f[210][210],tot=1,cur[N*N],ans,d[N];
struct node{int to,nxt,w;
}e[N*N+1000];
inl void add(int u,int v,int w) {//cout<<1<<endl;e[++tot].to=v;e[tot].w=w;e[tot].nxt=head[u];head[u]=tot;e[++tot].to=u;e[tot].w=0;e[tot].nxt=head[v];head[v]=tot;
}
inl bool bfs() {memset(d,0,sizeof(d));queue<int> q;d[1]=1;q.push(1);while(!q.empty()) {int u=q.front() ;q.pop();for(re int i=head[u];i;i=e[i].nxt) {int v=e[i].to;if(!d[v] && e[i].w) {d[v]=d[u]+1;q.push(v);if(v==n) return 1;}}}return 0;
}
inl int dfs(int u,int mf) {if(u==n) return mf;int tmp=0;for(int i=cur[u];i;i=e[i].nxt) {cur[u]=i;int v=e[i].to;if(d[v]==d[u]+1 && e[i].w) {int tmp1=dfs(v,min(mf,e[i].w));e[i].w-=tmp1;e[i^1].w+=tmp1;tmp+=tmp1;mf-=tmp1;if(!mf) break;}}if(!tmp) d[u]=0;return tmp;
}
inl void dinic() {while(bfs()) {memcpy(cur,head,sizeof head);ans+=dfs(1,100000000);}
}
int main() {n=read();m=read();x=read();//cout<<n<<" "<<m<<" "<<x<<endl;for(re int i=1;i<=m;i++) {int u=read(),v=read(),w=read();if(!f[u][v]) {add(u,v,w);f[u][v]=tot;}else{e[f[u][v]-1].w+=w;}}dinic();if(!ans) {puts("Orz Ni Jinan Saint Cow!");}else {int p=x/ans;if(p*ans<x) {p++;}printf("%d %d\n",ans,p);}return 0;
}

http://www.lryc.cn/news/437995.html

相关文章:

  • el-tree父子不互相关联时,手动实现全选、反选、子级全选、清空功能
  • 模板与泛型编程笔记(一)入门篇
  • 浅谈WebApi
  • 9月14日,每日信息差
  • 无人机控制与三维AI感知处理平台正式上线!
  • 9.11-kubeadm方式安装k8s
  • 限流,流量整形算法
  • 【C++知识扫盲】------C++ 中的引用入门
  • 【机器学习】6 ——最大熵模型
  • 小程序——生命周期
  • 基于微信小程序的宠物之家的设计与实现
  • 自定义EPICS在LabVIEW中的测试
  • 基于深度学习的农作物病害检测
  • 【C#】命名规范
  • 超级帐本(Hyperledger)
  • 如何精细优化网站关键词排名:实战经验分享
  • Ruoyi Cloud 本地启动
  • Nginx解析:入门笔记
  • 在 Mac 上安装双系统会影响性能吗,安装双系统会清除数据吗?
  • vue3提交按钮限制重复点击
  • Java | Leetcode Java题解之第395题至少有K个重复字符的最长子串
  • 20240915 每日AI必读资讯
  • 量化交易需要注意的关于股票交易挂单排队规则的问题
  • 应急响应实战---是谁修改了我的密码?
  • 知识的通用性
  • 36岁,大厂女程序员,中年失业后,我开始接受自己的平凡,并深耕自己
  • shader 案例学习笔记之mix函数
  • OpenAI草莓正式发布,命名o1
  • 心觉:以终为始,帮你精准实现目标
  • 【Kubernetes】linux centos安装部署Kubernetes集群