zkw费用流模板
2024-08-26 20:57:01
理论:http://www.cnblogs.com/acha/p/6735037.html
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> using namespace std; #define N 5001
#define M 50001 const int inf=1e9; int n,m,src,decc; int tot=; int front[N],to[M<<],nxt[M<<],from[M<<];
int val[M<<],cap[M<<]; int max_flow,cost; int dis[N];
bool vis[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void add(int u,int v,int w,int f)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; from[tot]=u; val[tot]=f; cap[tot]=w;
to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; from[tot]=v; val[tot]=-f; cap[tot]=;
} int augment(int now,int flow)
{
vis[now]=true;
if(now==decc)
{
cost+=-dis[src]*flow;
max_flow+=flow;
return flow;
}
int delta;
for(int i=front[now];i;i=nxt[i])
{
if(cap[i] && !vis[to[i]] && dis[to[i]]==dis[now]+val[i])
{
delta=augment(to[i],min(flow,cap[i]));
if(delta)
{
cap[i]-=delta;
cap[i^]+=delta;
return delta;
}
}
}
return ;
} bool retreat()
{
if(vis[decc]) return true;
int mi=inf;
for(int i=;i<=tot;i++)
{
if(cap[i] && vis[from[i]] && !vis[to[i]])
mi=min(mi,dis[from[i]]+val[i]-dis[to[i]]);
}
if(mi==inf) return false;
for(int i=;i<=n;++i)
if(vis[i]) dis[i]-=mi;
return true;
} void zkw()
{
do
{
memset(vis,false,sizeof(vis));
augment(src,inf);
}while(retreat());
cout<<max_flow<<' '<<cost;
} int main()
{
read(n); read(m); read(src); read(decc);
int u,v,w,f;
while(m--)
{
read(u); read(v); read(w);read(f);
add(u,v,w,f);
}
zkw();
}
最新文章
- js随机从数组中取出几个元素
- 【ArcGis for javascript从零开始】之一 ArcGis加载天地图
- Qt Meta Object System-元对象系统
- SQL server 2008 建立新用户
- Silverlight C#动态设置样式
- mac os 下如何清除/切换svn eclipse插件的用户
- Android 开发框架介绍
- 单片机usb转串口的时灵时不灵的解答
- C++ STL之pair常用指令
- Linux Shell——函数的使用
- python3网络编程之socketserver
- nRF24LE1/nRF31512烧录驱动开发
- 【翻译】浏览器渲染Rendering那些事:repaint、reflow/relayout、restyle
- 【PAT】我要通过!
- Pains and Sickness 学习笔记
- NHibernate初学者指南系列文章导航
- 在docker中运行jenkins实现代码自动发布到测试服务器
- __file__
- Borland.Delphi.dll
- plsql programming 10 日期和时间戳