bzoj1458 士兵占领

迷南。 2021-12-20 10:29 138阅读 0赞

[bzoj1458 士兵占领][bzoj1458]

> 有一个 \\(M\\times N\\) 的棋盘，有的格子是障碍。现在你要选择一些格子来放置一些士兵，一个格子里最多可以放置一个士兵，障碍格里不能放置士兵。我们称这些士兵占领了整个棋盘当满足第i行至少放置了 \\(L\_i\\) 个士兵, 第j列至少放置了 \\(C\_j\\) 个士兵。现在你的任务是要求使用最少个数的士兵来占领整个棋盘。
> 
> \\(M,\\ N\\leq100\\)

网络流，费用流

--------------------

建出每个为被删除的点 \\((i,\\ j)\\) ，这个点会对 \\(tid\_i,\\ tid\_j\\) 造成 \\(1\\) 的贡献。限制每行每列的士兵个数，就把每行每列建成点，连一条边限制容量即可。于是就建出了一个二分图。统计士兵个数可以考虑统计源点流出的容量数，因为每个士兵会流向每行每列两个节点，因此费用会是最终答案的两倍，除以二即可。

对于每行，连边 \\((tid\_i,\\ T,\\ L\_i,\\ 0)\\) ，每列同理

对于每个未被删除的点 \\((i,\\ j)\\) ，连边 \\((S,\\ id,\\ \\inf,\\ 1),\\ (id,\\ tid\_i,\\ 1,\\ 0),\\ (id,\\ tid\_j,\\ 1,\\ 0)\\)

我的代码交换了 \\(M,\\ N\\) ……

代码

#include <bits/stdc++.h> using namespace std; const int maxn = 11000, maxm = 1e5 + 10, inf = 1 << 30; int N, M, K; bool isv[105][105], vis[maxn]; int S, T, h[maxn], f[maxn], dis[maxn], pre[maxn]; struct edges { int nxt, to, w, c; edges(int _n = 0, int _t = 0, int _w = 0, int _c = 0) : nxt(_n), to(_t), w(_w), c(_c) {} } e[maxm]; queue <int> q; void addline(int u, int v, int w, int c) { static int cnt = 1; e[++cnt] = edges(h[u], v, w, c), h[u] = cnt; e[++cnt] = edges(h[v], u, 0, -c), h[v] = cnt; } bool spfa() { memset(dis, 0x3f, sizeof dis); q.push(S), dis[S] = 0, f[S] = inf; while (!q.empty()) { int u = q.front(); vis[u] = 0, q.pop(); for (int i = h[u]; i; i = e[i].nxt) { int v = e[i].to; if (e[i].w && dis[u] + e[i].c < dis[v]) { pre[v] = i; f[v] = min(f[u], e[i].w); dis[v] = dis[u] + e[i].c; if (!vis[v]) q.push(v), vis[v] = 1; } } } return dis[T] < 1e9; } void EK() { int res = 0, tmp = 0; while (spfa()) { tmp += f[T], res += f[T] * dis[T]; for (int u = T; u != S; u = e[pre[u] ^ 1].to) { e[pre[u]].w -= f[T], e[pre[u] ^ 1].w += f[T]; } } printf("%d", res >> 1); } int main() { int sr[105], sc[105]; scanf("%d %d %d", &N, &M, &K); S = N * M + N + M + 1, T = S + 1; for (int i = 1; i <= N; i++) { scanf("%d", sr + i); addline(N * M + i, T, sr[i], 0); } for (int i = 1; i <= M; i++) { scanf("%d", sc + i); addline(N * M + N + i, T, sc[i], 0); } for (int i = 1, x, y; i <= K; i++) { scanf("%d %d", &x, &y), isv[x][y] = 1; } int R[105], C[105]; memset(R, 0, sizeof R); memset(C, 0, sizeof C); for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { if (!isv[i][j]) { R[i]++, C[j]++; int tid = M * (i - 1) + j; addline(S, tid, inf, 1); addline(tid, N * M + i, 1, 0); addline(tid, N * M + N + j, 1, 0); } } } for (int i = 1; i <= N; i++) { if (R[i] < sr[i]) return puts("JIONG!"), 0; } for (int i = 1; i <= M; i++) { if (C[i] < sc[i]) return puts("JIONG!"), 0; } EK(); return 0; }

转载于:https://www.cnblogs.com/Juanzhang/p/10731448.html

[bzoj1458]: https://www.lydsy.com/JudgeOnline/problem.php?id=1458