【最大流FF模板】HDU1532&POJ1273
2024-08-25 22:22:10
参照《挑战程序设计竞赛》
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const int MAXN=;
const int INF=0x7fffffff;
int n,m;//n:edges,m:points
struct node
{
int to,pos,cap;
};
vector<node> E[MAXN];
int vis[MAXN]; void addedge(int u,int v,int w)
{
E[u].push_back((node){v,E[v].size(),w});
E[v].push_back((node){u,E[u].size()-,});
} int dfs(int s,int t,int f)
{
if (s==t) return f;
vis[s]=;//不要忘记这里要设置为访问过
for (int i=;i<E[s].size();i++)
{
node &tmp=E[s][i];
if (vis[tmp.to]== && tmp.cap>)
{
int delta=dfs(tmp.to,t,min(tmp.cap,f));
if (delta>)
{
tmp.cap-=delta;
E[tmp.to][tmp.pos].cap+=delta;
return delta;
}
}
}
return ;
} int maxflow(int u,int v)
{
int flow=;
for (;;)
{
memset(vis,,sizeof(vis));
int f=dfs(u,v,INF);
if (f==) return flow;
else flow+=f;
}
} int main()
{
while(~scanf("%d%d",&n,&m))
{
memset(E,,sizeof(E));
for (int i=;i<n;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
addedge(x,y,z);
}
cout<<maxflow(,m)<<endl;
}
return ;
}
最新文章
- ActionContext.getContext().getSession()
- 【Java EE 学习 49 上】【Spring学习第一天】【基本配置】
- 安装Python2.7环境
- ajax图片上传及FastDFS入门案例.
- java swing模仿随机频谱
- mybatis3批量更新 批量插入
- 利用模板在RM里部署VM
- MySQL(19):SQL语句(MySQL)大全
- ActionScript 3.0日期与时间管理(Date类)
- SSIS Package 配置多数据库连接语句
- Android开发之监听器
- Spring @RequestParam乱码问题
- (四)esp8266 MDNS域名服务
- Vue + webpack 项目实践
- Redis学习-持久化机制
- 【HDU - 5845】Best Division(xor-trie、01字典树、dp)
- MongDB篇,第四章:数据库知识4
- C/C++中的位运算
- 5.servlet 上传文件
- linux shell 压缩解压命令
热门文章
- C# 关于调用微信接口的代码
- fragment+tabhost与viewpager
- 有向有权图的最短路径算法--Dijkstra算法
- skb管理函数之skb_put、skb_push、skb_pull、skb_reserve
- 【bzoj3224】普通平衡树
- HIbernate学习笔记5 之 查询
- Leetcode 之Regular Expression Matching(31)
- django “如何”系列7:错误汇报
- 【转载】关于Python的Mixin模式
- js解析与序列化json数据(一)json.stringify()的基本用法