LibreOJ #115. 无源汇有上下界可行流
2024-08-26 19:29:54
二次联通门 : LibreOJ #115. 无源汇有上下界可行流
/* LibreOJ #115. 无源汇有上下界可行流 板子题
我也就会写写板子题了。。 */
#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring> const int BUF = ;
char Buf[BUF], *buf = Buf; void read (int &now)
{
for (now = ; !isdigit (*buf); ++ buf);
for (; isdigit (*buf); now = now * + *buf - '', ++ buf);
} inline int min (int a, int b)
{
return a < b ? a : b;
} #define Max 800
#define INF 1e8
int _S, _T; int low[Max << ], _in[Max]; class Net_Flow
{
private : int to[Max << ], _next[Max << ], flow[Max << ];
int C, list[Max << ], deep[Max << ], _tech[Max << ]; int S, T; public : inline void In (int u, int v, int w)
{
to[++ C] = v, _next[C] = list[u], list[u] = C;
to[++ C] = u, _next[C] = list[v], list[v] = C;
flow[C] = , flow[C - ] = w;
} void Clear ()
{
C = , S = _S, T = _T;
} int Flowing (int now, int Flow)
{
if (now == T || Flow == )
return Flow;
register int res = , pos;
for (int &i = _tech[now]; i; i = _next[i])
{
if (deep[to[i]] != deep[now] + || flow[i] == )
continue;
pos = Flowing (to[i], min (flow[i], Flow));
if (pos > )
{
flow[i] -= pos, res += pos, flow[i ^ ] += pos;
Flow -= pos; if (Flow <= ) break;
}
}
if (res != Flow) deep[now] = -;
return res;
} bool Bfs ()
{
std :: queue <int> Queue;
memset (deep, -, sizeof deep);
Queue.push (S), deep[S] = ; register int i, now;
for (; !Queue.empty (); Queue.pop ())
{
now = Queue.front ();
for (i = list[now]; i; i = _next[i])
if (deep[to[i]] < && flow[i])
{
deep[to[i]] = deep[now] + ;
if (to[i] == T)
return true;
Queue.push (to[i]);
}
}
return deep[T] != -;
} int Dinic ()
{
int res = ;
for (; Bfs (); )
{
for (int i = S; i <= T; ++ i)
_tech[i] = list[i];
res += Flowing (S, INF);
}
return res;
} void Print (const int &M)
{
printf ("YES\n");
for (int i = ; i <= M; ++ i)
printf ("%d\n", low[i] + flow[i << | ]);
}
};
Net_Flow Flow; //#define Local int Main ()
{ #ifdef Local freopen ("yukari.wife", "r", stdin);
#endif
fread (buf, , BUF, stdin); int N, M;
read (N);
read (M);
int u, v, up;
_S = , _T = N + , Flow.Clear (); for (int i = ; i <= M; ++ i)
{
read (u), read (v), read (low[i]), read (up);
Flow.In (u, v, up - low[i]);
_in[u] -= low[i], _in[v] += low[i];
}
int Total = ;
for (int i = ; i <= N; ++ i)
if (_in[i] > )
Total += _in[i], Flow.In (_S, i, _in[i]);
else if (_in[i] < )
Flow.In (i, _T, -_in[i]); if (Flow.Dinic () != Total)
return printf ("NO"), ;
else Flow.Print (M); return ;
}
int ZlycerQan = Main ();
int main (int argc, char *argv[]) {; }
最新文章
- RabbitMQ 开启WEB管理
- toUnsignedString详解
- JavaScript Patterns 5.9 method() Method
- 深入理解KMP算法之续篇
- struts2中的addActionError 、addFieldError、addActionMessage的方法
- SGU 223.Little Kings
- Java程序执行Linux命令
- 1、	Linux中的root用户切换(转载)
- 使用MVC模式开发一简单的销售额查询系统
- hibernate日志信息
- Apache OFBiz源码解读之MVC模型
- 读《图解HTTP》有感-(了解web及网络基础)
- Hbase中HMaster作用
- 子集三种生成方法 java
- day11.1函数进阶 列表集合 字典中的函数变量,函数作为形参
- 机器学习中数据清洗&;预处理
- 安装cactiez v11对windows和linux系统进行监控
- Java Debugging with Eclipse - Tutorial
- form的智能表单
- 用Python实现的数据结构与算法:链表