理论: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();
}

最新文章

  1. js随机从数组中取出几个元素
  2. 【ArcGis for javascript从零开始】之一 ArcGis加载天地图
  3. Qt Meta Object System-元对象系统
  4. SQL server 2008 建立新用户
  5. Silverlight C#动态设置样式
  6. mac os 下如何清除/切换svn eclipse插件的用户
  7. Android 开发框架介绍
  8. 单片机usb转串口的时灵时不灵的解答
  9. C++ STL之pair常用指令
  10. Linux Shell——函数的使用
  11. python3网络编程之socketserver
  12. nRF24LE1/nRF31512烧录驱动开发
  13. 【翻译】浏览器渲染Rendering那些事:repaint、reflow/relayout、restyle
  14. 【PAT】我要通过!
  15. Pains and Sickness 学习笔记
  16. NHibernate初学者指南系列文章导航
  17. 在docker中运行jenkins实现代码自动发布到测试服务器
  18. __file__
  19. Borland.Delphi.dll
  20. plsql programming 10 日期和时间戳

热门文章

  1. Beta 冲刺1
  2. 剑指offer:旋转数组的最小数字
  3. 网页访问过程(基于CDN)
  4. 结队第二次作业——WordCount进阶需求
  5. 通过分析java heap dump解决生产问题
  6. pycharm 修改新建文件时的头部模板
  7. [微软官方]SQLSERVER的兼容级别
  8. [转帖]USB-C和Thunderbolt 3连接线你搞懂了吗?---没搞明白.
  9. [微软官方]FSUTIL
  10. mysql索引的优化