题目地址:https://www.luogu.com.cn/problem/P3254
分析&做法
- 这是一道比较简单的【网络流24题】
- 很容易想到二分图
- 左边$M$个点代表$M$个单位,右边$N$个点代表每一个桌子,对于$M$个公司,每一个公司向所有桌子连边,因为一个公司在一个桌子上只能派一个人,所以边权为$1$
- 源点$S$连向左边的$M$个点,边权为该单位的人数$ri$,意思是这个公司派出了$ri$个人
- 右边的$N$个点连向汇点$T$,边权为该桌子的容量$ci$,意思是这个桌子最多坐$ci$个人
- 这一切就顺理成章的想出来了,最大流就是满足条件下最多能就做的人数
- 如果最大流等于总人数,则输出$1$,否则输出$0$
- 至于输出方案,我的方法是最后枚举$M$个公司的$N$条出边,如果残留流量为$0$,就说明派了一个人到那个桌子上,输出就好了
代码
#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <vector> #define maxN 500 #define maxM 100000 #define INF 2e9 using namespace std; int N, M, S, T, Ans, Sum; struct Edge { int nxt, dis, to; } e[maxM]; int cnte = 1, head[maxN]; inline void Add(int i, int j, int k) { e[ cnte].dis = k, e[cnte].nxt = head[i], e[cnte].to = j, head[i] = cnte; e[ cnte].dis = 0, e[cnte].nxt = head[j], e[cnte].to = i, head[j] = cnte; } int dep[maxN]; bool bfs() { queue<int> Q; memset(dep, 0, sizeof(dep)); dep[S] = 1, Q.push(S); while (!Q.empty()) { int u = Q.front(); Q.pop(); for (int v, i = head[u]; i; i = e[i].nxt) { if (e[i].dis && !dep[v = e[i].to]) { dep[v] = dep[u] 1; Q.push(v); } } } return dep[T]; } vector<int> p[maxN]; int dfs(int u, int in) { if (u == T) return in; int out = 0; for (int v, i = head[u]; i && in; i = e[i].nxt) { if (e[i].dis && dep[v = e[i].to] == dep[u] 1) { int tmp = dfs(v, min(in, e[i].dis)); if (tmp > 0 && 1 <= u && u <= M) p[u].push_back(v - M); e[i].dis -= tmp, e[i ^ 1].dis = tmp; in -= tmp, out = tmp; } } if (!out) dep[u] = 0; return out; } int main() { cin >> M >> N; S = N M 1, T = S 1; for (int i = 1, r; i <= M; i) { cin >> r, Sum = r; Add(S, i, r); } for (int i = M 1, c; i <= M N; i) { cin >> c, Add(i, T, c); for (int j = 1; j <= M; j) { Add(j, i, 1); } } while (bfs()) Ans = dfs(S, INF); if (Ans == Sum) printf("1n"); else { printf("0n"); return 0; } for (int u = 1; u <= M; u) { for (int i = head[u]; i; i = e[i].nxt) { if (!e[i].dis) printf("%d ", e[i].to - M); } printf("n"); } return 0; }