费用流+SPFA ||Luogu P3381【模板】最小费用最大流
2024-09-07 00:59:11
题面:【模板】最小费用最大流
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#define ll long long
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
inline ll rd(){
ll x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return f*x;
}
const int maxn=,maxm=;
int N,M,num_edge=-,edge_head[maxn],S,T,u,v,w,f,pre[maxn];
ll Dis[maxn],Fw[maxn],mxfw,mndis;
bool vis[maxn];
queue<int>Q;
struct Edge{int to,nx,from;ll dis,fw;}edge[maxm<<];
inline void Add_edge(int from,int to,ll fw,ll dis){
edge[++num_edge].nx=edge_head[from];
edge[num_edge].from=from;
edge[num_edge].to=to;
edge[num_edge].fw=fw;
edge[num_edge].dis=dis;
edge_head[from]=num_edge;
return;
}
inline bool SPFA(){
// for(int i=1;i<=N;i++)
// Dis[i]=Fw[i]=1ll<<60;
memset(Dis,0x7f,sizeof(Dis));
memset(Fw,0x7f,sizeof(Fw));
memset(vis,,sizeof(vis));
pre[S]=pre[T]=-;//Imp
Q.push(S);
vis[S]=;
Dis[S]=;
while(!Q.empty()){
int x=Q.front();
Q.pop();
vis[x]=;
for(int i=edge_head[x];i!=-;i=edge[i].nx){
int y=edge[i].to;
if(edge[i].fw&&edge[i].dis+Dis[x]<Dis[y]){
Dis[y]=edge[i].dis+Dis[x];
Fw[y]=min(Fw[x],edge[i].fw);//这一步和Dinic差不多
pre[y]=i;
if(vis[y]==){
Q.push(y);
vis[y]=;
}
}
}
}
if(pre[T]!=-)return ;
return ;
}
inline void FYL(){
mxfw=mndis=;
while(SPFA()){
mxfw+=Fw[T];
mndis+=Dis[T]*Fw[T];
for(int i=pre[T];i!=-;i=pre[edge[i].from]){
edge[i].fw-=Fw[T];
edge[i^].fw+=Fw[T];
}
}
return;
}
int main(){
memset(edge_head,-,sizeof(edge_head));
N=rd();M=rd();S=rd();T=rd();
for(int i=;i<=M;i++){
u=rd();v=rd();w=rd();f=rd();
Add_edge(u,v,w,f);
Add_edge(v,u,,-f);
}
FYL();
printf("%lld %lld\n",mxfw,mndis);
return ;
}
By:AlenaNuna
最新文章
- 【Reading Note】算法读书杂记
- *HDU 1237 栈
- 【leetcode】Min Stack -- python版
- Extjs treePanel 后台Json的两种构建方法
- C/C++中堆与栈
- 学习Slim Framework for PHP v3 (七)--route middleware怎么被add进来的?
- 2013腾讯编程马拉松初赛第二场(3月22日) 小Q系列故事——为什么时光不能倒流 ---好水!!
- MYSql查詢一段時間記錄
- linux系统文件夹的作用 good
- Struts1、Struts2的线程安全问题
- 重写AlertView(用block)
- ural1424 Minibus
- LGTB与序列 状压dp
- Centos7.0关闭防火墙
- mysql常用基础操作语法(十一)~~字符串函数【命令行模式】
- Minieye杯第十五届华中科技大学程序设计邀请赛网络赛D	Grid(简单构造)
- 关于MySQL锁的详解
- 通过ICE轻松部署WES7镜像
- pytesseract使用的坑
- 安卓测试【一】android sdk环境变量配置