题面:【模板】最小费用最大流

代码:

 #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

最新文章

  1. 【Reading Note】算法读书杂记
  2. *HDU 1237 栈
  3. 【leetcode】Min Stack -- python版
  4. Extjs treePanel 后台Json的两种构建方法
  5. C/C++中堆与栈
  6. 学习Slim Framework for PHP v3 (七)--route middleware怎么被add进来的?
  7. 2013腾讯编程马拉松初赛第二场(3月22日) 小Q系列故事——为什么时光不能倒流 ---好水!!
  8. MYSql查詢一段時間記錄
  9. linux系统文件夹的作用 good
  10. Struts1、Struts2的线程安全问题
  11. 重写AlertView(用block)
  12. ural1424 Minibus
  13. LGTB与序列 状压dp
  14. Centos7.0关闭防火墙
  15. mysql常用基础操作语法(十一)~~字符串函数【命令行模式】
  16. Minieye杯第十五届华中科技大学程序设计邀请赛网络赛D Grid(简单构造)
  17. 关于MySQL锁的详解
  18. 通过ICE轻松部署WES7镜像
  19. pytesseract使用的坑
  20. 安卓测试【一】android sdk环境变量配置

热门文章

  1. java 栈和栈帧
  2. GoldenGate—AUTORESTART配置
  3. 生成base64位图片验证码
  4. Git-Runoob:Git 分支管理
  5. ES6实现数组去重
  6. Linux_文件系统、磁盘分区_RHEL7
  7. 系统分析与设计HW5
  8. Oracle 查询库文件信息
  9. LeetCode.867-转置矩阵(Transpose Matrix)
  10. 深入理解java:1.3.2 JVM监控与调优