基础网络流,增加s和t,同时对于每个结点分裂为流入结点和流出结点。EK求最大流,判断最大流是否等于当前总人数。

 /* 304E */
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 const int maxn = ;
int F[maxn][maxn];
int P[maxn], a[maxn];
bool visit[maxn];
int ans[maxn][maxn];
int ai[maxn], bi[maxn], ci[maxn];
int n, m, s = , t;
bool flag = true; bool bfs() {
int u, v;
queue<int> Q; memset(a, , sizeof(a));
a[s] = INT_MAX;
Q.push(s);
P[s] = s; while (!Q.empty()) {
u = Q.front();
Q.pop();
for (v=; v<=t; ++v) {
if (!a[v] && F[u][v]) {
P[v] = u;
Q.push(v);
a[v] = min(a[u], F[u][v]);
}
}
} return a[t]==;
} int Edmonds_Karp() {
int u, v;
int ans = ; while () {
if (bfs())
break;
for (u=t,v=P[u]; u!=s; u=v, v=P[u]) {
F[u][v] += a[t];
F[v][u] -= a[t];
}
ans += a[t];
}
return ans;
} int main() {
int i, j, k;
int s1, s2; #ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif scanf("%d %d", &n, &m);
t = n+n+;
memset(F, , sizeof(F));
memset(ans, , sizeof(ans));
s1 = s2 = ; for (i=; i<=n; ++i) {
scanf("%d", &ai[i]);
s1 += ai[i];
F[][i] = ai[i];
} for (i=; i<=n; ++i) {
scanf("%d", &bi[i]);
s2 += bi[i];
F[i][i+n] = INT_MAX;
F[i+n][t] = bi[i];
} for (i=; i<m; ++i) {
scanf("%d %d", &j, &k);
F[j][k+n] = INT_MAX;
F[k][j+n] = INT_MAX;
} flag = s1==s2;
if (flag) {
flag = Edmonds_Karp() == s1;
} if (flag) {
for (i=; i<=n; ++i)
for (j=n+; j<t; ++j)
ans[i][j-n] = F[j][i];
puts("YES");
for (i=; i<=n; ++i) {
for (j=; j<=n; ++j)
printf("%d ", ans[i][j]);
putchar('\n');
}
} else {
puts("NO");
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}

最新文章

  1. redis命令1
  2. 成 功 的 背 后 !( 致给所有IT人员)
  3. 《SSM框架搭建》三.整合spring web
  4. psql-05数据库,模式
  5. 经典实用jQuery soChange幻灯片实例演示
  6. VMware虚拟机网络环境类型
  7. pc加入域认证细节
  8. 如何写一个漂亮的Liferay Theme 6.2
  9. 在MVC5中的使用Ninject
  10. 读苹果开发文档时遇到瓶颈,转而花2天看了Objc基本语法
  11. $(window).on(&quot;load&quot;,function(){} 和 $(document).ready(function() {}
  12. mybatis映射异常
  13. 解决centos7上system tools - setting无法打开的问题
  14. java类的生命周期
  15. mediainfo使用
  16. 四、K8S
  17. PHP文件上传与下载
  18. Javascript网页特效开发技巧
  19. PHP代码审计笔记--代码执行漏洞
  20. oracle锁表查询

热门文章

  1. JavaScript 应用开发 #5:为完成的任务添加样式
  2. as3 打开窗口类
  3. 过滤器(filter)实现用户登录拦截
  4. python matplotlib.plot画图显示中文乱码的问题
  5. (转)apache的keepalive和keepalivetimeout(apache优化)
  6. cas系列(三)--HTTP和HTTPS、SSL
  7. boost::xml——基本操作以及中文乱码解决方案 (续)
  8. jQuery插件综合应用(二)文字为主的页面
  9. js 中对象属性的特性
  10. android按行读取文件内容的几个方法