二次联通门 : 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[]) {; }

最新文章

  1. RabbitMQ 开启WEB管理
  2. toUnsignedString详解
  3. JavaScript Patterns 5.9 method() Method
  4. 深入理解KMP算法之续篇
  5. struts2中的addActionError 、addFieldError、addActionMessage的方法
  6. SGU 223.Little Kings
  7. Java程序执行Linux命令
  8. 1、 Linux中的root用户切换(转载)
  9. 使用MVC模式开发一简单的销售额查询系统
  10. hibernate日志信息
  11. Apache OFBiz源码解读之MVC模型
  12. 读《图解HTTP》有感-(了解web及网络基础)
  13. Hbase中HMaster作用
  14. 子集三种生成方法 java
  15. day11.1函数进阶 列表集合 字典中的函数变量,函数作为形参
  16. 机器学习中数据清洗&amp;预处理
  17. 安装cactiez v11对windows和linux系统进行监控
  18. Java Debugging with Eclipse - Tutorial
  19. form的智能表单
  20. 用Python实现的数据结构与算法:链表

热门文章

  1. SSM整合所需的maven配置文件
  2. vmware vSphere Data Protection 6.1 --------1-部署
  3. Self寄宿
  4. 【转载】C#使用Except方法求取两个List集合的差集数据
  5. Fortify漏洞之Open Redirect(开放式重定向)
  6. 解决 google 浏览器记住密码导致输入框样式改变(变成淡黄色背景)
  7. HIVE常用命令之MSCK REPAIR TABLE
  8. Django中使用geetest验证
  9. Hbase Region in transition问题解决
  10. Java--8--新特性--Lambda