输入格式 第一行有一个整数n。 第二行有 n个整数 a。 第三行有 n 个整数 bi。 接下来 n 行,每行有n 个整数 ci,j。 输出格式 一行两个整数,最多入学人数与最少花费
时间: 2024-03-23 20:42:53 浏览: 79
以下是完整的C++代码:
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int N = 210, M = (N * N + N) * 2, INF = 0x3f3f3f3f;
int n, S, T;
int a[N], b[N], c[N][N];
int h[N], e[M], f[M], w[M], ne[M], idx;
int pre[N], incf[N], d[N];
bool st[N];
void add(int a, int b, int c, int d) {
e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx++;
e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx++;
}
bool spfa() {
queue<int> q;
memset(d, 0xcf, sizeof d);
memset(incf, 0, sizeof incf);
q.push(S);
d[S] = 0, incf[S] = INF, st[S] = true;
while (!q.empty()) {
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (f[i] && d[j] < d[t] + w[i]) {
d[j] = d[t] + w[i];
incf[j] = min(incf[t], f[i]);
pre[j] = i;
if (!st[j]) {
q.push(j);
st[j] = true;
}
}
}
}
return incf[T] > 0;
}
void EK() {
int flow = 0, cost = 0;
while (spfa()) {
int t = incf[T];
flow += t, cost += d[T] * t;
for (int i = T; i != S; i = e[pre[i] ^ 1]) {
f[pre[i]] -= t;
f[pre[i] ^ 1] += t;
}
}
cout << flow << " " << cost << endl;
}
int main() {
memset(h, -1, sizeof h);
cin >> n;
S = 0, T = n * 2 + 1;
for (int i = 1; i <= n; i++) {
cin >> a[i];
add(S, i, a[i], 0);
add(i, T, a[i], 0);
}
int sum_b = 0;
for (int i = 1; i <= n; i++) {
cin >> b[i];
sum_b += b[i];
add(S, i + n, b[i], 0);
add(i + n, T, b[i], 0);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
cin >> c[i][j];
if (c[i][j] != -1)
add(i, j + n, INF, c[i][j]);
}
add(T - 1, S, INF, 0);
if (EK() < sum_b) cout << -1 << endl;
return 0;
}
```
首先,读入输入数据,然后按照网络流的建图方式,将每个小区看作源点,每个学校看作汇点,源点向汇点连一条容量为 $1$,费用为 $c_{i,j}$ 的边。如果 $c_{i,j}=-1$,表示该学校不能容纳该小区的学生,那么就将该边容量设为 $0$。所有源点的总供给量为 $\sum a_i$,所有汇点的总需求量为 $\sum b_i$,将其连接到超级源点和超级汇点上,容量为对应量,费用为 $0$。
建图完成后,对这个图跑费用流算法即可。这里使用的是费用流的一种变种——最小费用最大流算法,即先求出最大流,然后在最大流的基础上,不断寻找增广路,并将增广路上的流量增加,直到无法找到增广路为止。具体实现中,可以使用 SPFA 或 Bellman-Ford 等算法来寻找增广路。
最后输出最大流(即最多入学人数)和最小费用(即最少花费)。如果最大流小于总需求量,说明有学校无法满足需求,输出 $-1$。
时间复杂度为 $O(f \cdot m \cdot \log n)$,其中 $f$ 为最大流量,$m$ 为边数,$n$ 为节点数。
阅读全文