loj #116. 有源汇有上下界最大流
2024-10-13 16:21:06
有源汇有上下界最大流,->上下界网络流
注意细节,重置cur和dis数组时,有n+2个点
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream> using namespace std; const int N = ;
const int INF = 1e9; struct Edge {
int to,nxt,c;
}e[];
int head[N],dis[N],cur[N],M[N];
int q[],L,R;
int n,m,S,T,tot = ,Sum; inline char nc() {
static char buf[],*p1 = buf,*p2 = buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2)?EOF:*p1++;
}
inline int read() {
int x = ,f = ;char ch = nc();
for (; ch<''||ch>''; ch=nc()) if(ch=='-') f=-;
for (; ch>=''&&ch<=''; ch=nc()) x=x*+ch-'';
return x * f;
}
void add_edge(int u,int v,int c) {
e[++tot].to = v,e[tot].c = c,e[tot].nxt = head[u],head[u] = tot;
}
bool bfs() {
for (int i=; i<=n+; ++i) // n+2
cur[i] = head[i],dis[i] = -;
L = ,R = ;
q[++R] = S;
dis[S] = ;
while (L <= R) {
int u = q[L++];
for (int i=head[u]; i; i=e[i].nxt) {
int v = e[i].to;
if (dis[v] == - && e[i].c > ) {
dis[v] = dis[u] + ;
q[++R] = v;
if (v == T) return true;
}
}
}
return false;
}
int dfs(int u,int flow) {
if (u == T) return flow;
int used = ;
for (int &i=cur[u]; i; i=e[i].nxt) {
int v = e[i].to;
if (dis[v] == dis[u] + && e[i].c > ) {
int tmp = dfs(v,min(e[i].c,flow-used));
if (tmp > ) {
e[i].c -= tmp;e[i^].c += tmp;
used += tmp;
if (used == flow) break;
}
}
}
if (used != flow) dis[u] = -;
return used;
}
int dinic(int s,int t) {
S = s,T = t;
int ans = ;
while (bfs()) ans += dfs(S,INF);
return ans;
}
int main () {
freopen("1.txt","r",stdin);
n = read(),m = read();
int s = read(),t = read();
int ss = n+,tt = n+;
for (int i=; i<=m; ++i) {
int u = read(),v = read(),b = read(),c = read();
add_edge(u,v,c-b);
add_edge(v,u,);
M[u] -= b;M[v] += b;
}
for (int i=; i<=n; ++i) {
if (M[i] > ) add_edge(ss,i,M[i]),add_edge(i,ss,),Sum += M[i];
if (M[i] < ) add_edge(i,tt,-M[i]),add_edge(tt,i,);
}
add_edge(t,s,INF);
add_edge(s,t,);
if (dinic(ss,tt) != Sum) {
puts("please go home to sleep");
return ;
}
int ans = e[tot].c;
e[tot].c = ;e[tot ^ ].c = ;
ans += dinic(s,t);
printf("%d\n",ans);
return ;
}
最新文章
- fileinput模块
- iOS大神牛人的博客集合
- 2. npm 的使用
- PB 简单笔记!
- 黄聪:手机移动端建站Jquery+CSS3+HTML5触屏滑动特效插件、实现触屏焦点图、图片轮展图
- Fragment详解
- WPF的TextBox的焦点获取与失去焦点的死循环解决方案
- ASP.NET中默认的一级目录
- 【Android UI设计和开发】动画(Animation)详细说明(一)
- 再起航,我的学习笔记之JavaScript设计模式29(节流模式)
- MySQL之索引详解
- shell编程变量介绍与表达式详解
- 弱省胡策 Magic
- VB.NET 编程元素支持更改总结
- WTL CHyperLink类的使用(超链接)
- 牛客多校第三场 A—pacm team (4维背包加路径压缩)
- Spark安装过程纪录
- Swift可向上滑移出界面的欢迎页简单封装
- 反卷积Deconvolution
- std::thread函数传参拷贝次数
热门文章
- mui 下拉刷新和上拉加载
- webpack 构建 node_modules 中公司内部组件
- Spring Boot(十六):使用 Jenkins 部署 Spring Boot
- Asp.net MVC 中Ajax的使用
- Scrum Meeting day 3
- 《Linux内核分析》第七周学习笔记
- SE Springer小组之《Spring音乐播放器》需求分析说明书二
- net license tool, EasyLicense !
- 8-Python3从入门到实战—基础之数据类型(集合-Sets)
- Analyze a docker instance start failure