1 solutions
-
1
本文适合初学者阅读。
dalao勿喷对于这种类型的题目,又是增加,又是减少的,我们可以使用网络流进行转化。
说句废话:
网络流这个东西,趣味十足,上可顶替匈牙利算法,下可转化动态规划。它似水一般灵活,总是可以出乎意料地解决问题。好了,说回来,看到这种题目,你有什么疑惑?
说说我的吧:
- 信息这么多( 和 ),怎么保存?
- 这么多的点,无组织,无纪律,怎么办呢?
- 这情况也太多了吧,怎么
暴搜思考呢? - 即使知道可行,这题的输出怎么办呢?
真恶心
我们从网络最大流的角度一个一个来思考吧!
1. 信息这么多,怎么保存?
我们可以把一个点的信息一分为2,让他们整齐罗列。
千万不要误以为 和 为节点,图中只是形象化地阐述“把一个点的信息一分为2”
2. 这么多的点,无组织,无纪律,怎么办呢?
那就找两个领导把他们汇总起来,这两个领导叫做源点以及汇点。
那流量是多少呢?
看图!
看左半部分,点 的流量为 。
同理,右半部分流量为 。
中间部分暂不考虑为什么要这样干呢?
现在假设 点有无穷无尽的水资源。
那么可以往每个左边的河道里塞满水,也就是对于左边的点 (图中是靠近红点的四个点)的初始值为 。
也就是对应题目中“每个点初始时有 个人”的条件。
同样的道理,经过中间一番乱七八糟的处理后,从右边流出的水应为 ,表示最终处理后,对于右边的点 (图中是靠近绿点的四个点)最终为 。
也就是对应题目中“每个点最终有 个人”的条件。
3. 这情况也太多了吧,怎么思考呢?
也就是考虑中间部分。
首先,有些人可以选择留下。那么对于这些点的水,随它们流,连接 条边,流量为 。
当然,如果有边相连,那也随便流,连接 条边(与题目中的 意义相同),如图(假设有这些边)。
于是乎,跑一遍Dinic算法足矣!
- 即使知道可行,这题的输出怎么办呢?
真恶心
众所周知,Dinic会在找到增广路时,建立反边,以便反悔。那么这些反边,就是我们利用的对象。
一条边的反边的权值不就是流过该边的流量吗?
把中间部分的每条反边揪出来,在保存到一个数组里即可。
AC Code
#include <iostream> #include <cstring> #include <algorithm> #include <numeric> const int N = 210, M = 1410, INF = 1e9; struct Node { int to; int next; int w; }e[M]; int head[N], cur[N], idx = 1; void add(int a, int b, int c) // 加边 { idx++; e[idx].to = b; e[idx].next = head[a]; e[idx].w = c; head[a] = idx; idx++; e[idx].to = a; e[idx].next = head[b]; e[idx].w = 0; head[b] = idx; } int n, m; int a[N]; int b[N]; int S, T; int sum1, sum2; // sum1:a sum2:b int d[N]; bool bfs() { static int q[N]; // 队列 int hh = 0, tt = 0; memset(d, 0, sizeof(d)); q[0] = S; cur[S] = head[S]; d[S] = 1; while (hh <= tt) { int t = q[hh++]; for (int i = head[t]; i; i = e[i].next) { int to = e[i].to; if (!d[to] && e[i].w) { cur[to] = head[to]; d[to] = d[t] + 1; q[++tt] = to; if (to == T) return true; } } } return false; } int dinic(int u, int limit) { if (u == T) return limit; int rest = limit; for (int i = cur[u]; i && rest; i = e[i].next) { cur[u] = i; int to = e[i].to; if (d[to] == d[u] + 1 && e[i].w) { int k = dinic(to, std::min(rest, e[i].w)); if (!k) d[to] = 0; rest -= k; e[i].w -= k; e[i ^ 1].w += k; } } return limit - rest; } int map[N][N]; // 记录反边信息,即结果 int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cin >> n >> m; for (int i = 1; i <= n; i++)std::cin >> a[i]; for (int i = 1; i <= n; i++)std::cin >> b[i]; sum1 = std::accumulate(a + 1, a + n + 1, 0); // 求和 sum2 = std::accumulate(b + 1, b + n + 1, 0); if(sum1 != sum2) //直接排除 { std::cout << "NO" << '\n'; return 0; } for (int i = 1; i <= n; i++) add(0, i, a[i]); // 左 for (int i = n + 1; i <= n * 2; i++) add(i, n * 2 + 1, b[i - n]); // 右 for (int i = 1; i <= n; i++) add(i, i + n, INF); // 中1 for (int i = 1; i <= m; i++) // 中2 { int a, b; std::cin >> a >> b; add(a, b + n, INF); add(b, a + n, INF); } S = 0, T = n * 2 + 1; auto query = [&]() // Dinic 模板 { int maxflow = 0, flow = 0; while (bfs()) { while (flow = dinic(S, INF)) { maxflow += flow; } } return maxflow; }; if (query() != sum1) // 直接排除 { std::cout << "NO" << '\n'; return 0; } else // 扣反边 { std::cout << "YES" << '\n'; int t = 4 * n + 2; for (int i = 1; i <= 2 * m + n; i++) { map[e[t ^ 1].to][e[t].to - n] += e[t ^ 1].w; // 注意要 -n t += 2; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { std::cout << map[i][j] << ' '; } std::cout << '\n'; } } return 0; }
码字不易,点个赞吧!
- 1
Information
- ID
- 4756
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 7
- Tags
- # Submissions
- 1
- Accepted
- 1
- Uploaded By