题解【CF1250K Projectors】
Jayun
·
·
题解
Projectors
题面
每堂讲课必须使用一个高清投影仪，而研讨会可以使用普通或高清投影仪。
给定讲课和研讨会的时间区间，构造一个投影仪的分配方案。
$n,m,x,y \leq 300, a_i,b_i,p_i,q_i \leq 10^6$。
## 题解
厉害的建模题。
分配普通投影仪的分配时不需要考虑每个讲课的区间具体是什么，只需要知道每个时刻被多少讲课所包含。以此为启发考虑到网络流。
先离散化时间，以时间轴为基础建图。我们考虑的是普通投影仪，就把其**最多剩余量**作为流量：
- 经过 $i\rightarrow i+1$ 最多剩余 $\min(y,x+y-(\sigma_x+\sigma_y))$ 个普通投影仪，其中 $\sigma_x,\sigma_y$ 分别表示讲课数量和研讨会数量。那么就连一条 $(i,i+1)$ 流量为 $\min(y,x+y-(\sigma_x+\sigma_y))$ 的边。
- 对于一个研讨会 $(p_i,q_i)$，连一条 $(p_i,q_i)$ 流量为 $1$ 的边。
这样建图，假设到了时间 $p_x$，如果流走了研讨会的边，说明此研讨会消耗了一个普通投影仪，如果走的是 $(p_x,p_x+1)$ 的边就是高清投影仪。
对于不合法，建图连边的时候若投影仪符合式子就不合法、最终流量不为 $y$ 不合法。
对于构造合法方案，开两个栈贪心即可。
## 代码
### 小问题
奇怪的是，网络流用邻接表会有错误（可能只是我的问题，还望指出），这个是错误代码：
```cpp
const int N = 610 * 2;
inline ll Read() {
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
namespace Main {
int n, m, x, y;
int a[N], b[N];
int sumX[N], sumY[N];
int dtmp[N << 1], tot;
int head[N << 1], cnt;
struct Edge {
int to; ll w; int op, nxt;
} e[N * 5];
void add_edge(int u, int v, ll w) {
e[++cnt] = (Edge) {v, w, cnt ^ 1, head[u]}, head[u] = cnt;
e[++cnt] = (Edge) {u, 0, cnt ^ 1, head[v]}, head[v] = cnt;
}
struct NetworkFlow {
const int inf = 707406378;
int S, T;
int dis[N];
queue <int> q;
bool bfs() {
while (!q.empty()) q.pop();
memset (dis, 127 / 3, sizeof dis);
dis[S] = 0;
q.push(S);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (dis[v] > dis[u] + 1 && e[i].w) {
dis[v] = dis[u] + 1;
if (v == T) return 1;
q.push(v);
}
}
}
return 0;
}
ll dfs (int u, ll flow) {
if (u == T) return flow;
ll sum = 0;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (dis[v] == dis[u] + 1 && e[i].w) {
ll f = dfs(v, min(e[i].w, flow - sum));
if (!f) dis[v] = -1;
e[i].w -= f;
e[e[i].op].w += f;
sum += f;
if (sum == flow) break;
}
}
return sum;
}
ll dinic () { ll ret = 0; for (; bfs(); ret += dfs(S, inf)); return ret; }
} nf;
vector <int> st[N], en[N];
int id[N];
int stX[N], stY[N];
int Ans[N];
void clr () {
for (int i = 1; i <= tot; i++) {
st[i].clear();
en[i].clear();
}
tot = 0, cnt = 1;
memset (Ans, 0, sizeof Ans);
memset (head, 0, sizeof head);
memset (sumX, 0, sizeof sumX);
memset (sumY, 0, sizeof sumY);
}
int main () {
for (int t = Read(); t--; clr()) {
n = Read(), m = Read(), x = Read(), y = Read();
for (int i = 1; i <= n; i++) a[i] = Read(), b[i] = Read(), dtmp[++tot] = a[i], dtmp[++tot] = b[i];
for (int i = 1; i <= m; i++) a[i + n] = Read(), b[i + n] = Read(), dtmp[++tot] = a[i + n], dtmp[++tot] = b[i + n];
sort (dtmp + 1, dtmp + 1 + tot);
tot = unique (dtmp + 1, dtmp + 1 + tot) - dtmp - 1;
for (int i = 1; i <= n + m; i++) {
a[i] = lower_bound(dtmp + 1, dtmp + 1 + tot, a[i]) - dtmp;
b[i] = lower_bound(dtmp + 1, dtmp + 1 + tot, b[i]) - dtmp;
if (i <= n) sumX[a[i]]++, sumX[b[i]]--;
else sumY[a[i]]++, sumY[b[i]]--;
st[a[i]].emplace_back(i);
en[b[i]].emplace_back(i);
}
for (int i = n + m; i >= n + 1; i--) {
add_edge(a[i], b[i], 1);
id[i] = cnt - 1;
}
bool flag = 1;
for (int i = 1; i <= tot; i++) {
sumX[i] += sumX[i - 1], sumY[i] += sumY[i - 1];
if (i < tot)add_edge(i, i + 1, min(y, x + y - sumX[i] - sumY[i]));
if (sumX[i] > x || x + y - (sumX[i] + sumY[i]) < 0) {
puts("NO"); flag = 0; break;
}
}
if (!flag) continue;
nf.S = tot + 5, nf.T = nf.S + 1;
add_edge(nf.S, 1, y);
add_edge(tot, nf.T, nf.inf);
if(nf.dinic() != y) { puts("NO"); continue; }
puts("YES");
int topX = 0, topY = 0;
for (int i = 1; i <= x; i++) stX[++topX] = i;
for (int i = x + 1; i <= x + y; i++) stY[++topY] = i;
for (int i = 1; i <= tot; i++) {
for (int j : en[i]) {
if (Ans[j] <= x) stX[++topX] = Ans[j];
else stY[++topY] = Ans[j];
}
for (int j : st[i]) {
if (j <= n || e[id[j]].w) Ans[j] = stX[topX--];
else Ans[j] = stY[topY--];
}
}
for (int i = 1; i <= n + m; i++) printf ("%d ", Ans[i]); putchar(10);
}
return 0;
}
}
int main () {
// freopen(".in", "r", stdin);
// freopen("1.out", "w", stdout);
Main::main();
return 0;
}
```
### AC 代码
下面是 AC 代码：
```cpp
const int N = 2e4 + 5;
inline ll Read() {
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
namespace Main {
int n, m, x, y;
int a[N], b[N];
int sumX[N], sumY[N];
int dtmp[N], tot;
struct Edge {
int to; ll w; int op;
};
vector <Edge> G[N];
void add_edge(int u, int v, ll w) {
G[u].emplace_back((Edge) {v, w, G[v].size()});
G[v].emplace_back((Edge) {u, 0, G[u].size() - 1});
}
struct NetworkFlow {
const int inf = 707406378;
int S, T;
int dis[N];
queue <int> q;
bool bfs() {
while (!q.empty()) q.pop();
memset (dis, 127 / 3, sizeof dis);
dis[S] = 0;
q.push(S);
while (!q.empty()) {
int u = q.front(); q.pop();
for (auto i : G[u]) {
int v = i.to;
if (dis[v] > dis[u] + 1 && i.w) {
dis[v] = dis[u] + 1;
if (v == T) return 1;
q.push(v);
}
}
}
return 0;
}
ll dfs (int u, ll flow) {
if (u == T) return flow;
ll sum = 0;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i].to;
if (dis[v] == dis[u] + 1 && G[u][i].w) {
ll f = dfs(v, min(G[u][i].w, flow - sum));
if (!f) dis[v] = -1;
G[u][i].w -= f;
G[v][G[u][i].op].w += f;
sum += f;
if (sum == flow) break;
}
}
return sum;
}
ll dinic () { ll ret = 0; for (; bfs(); ret += dfs(S, inf)); return ret; }
} nf;
vector <int> st[N], en[N];
int id[N];
int stX[N], stY[N];
int Ans[N];
void clr () {
for (int i = 1; i <= tot; i++) {
st[i].clear();
en[i].clear();
}
for (int i = 1; i <= n + m + 5; i++) G[i].clear();
tot = 0;
memset (Ans, 0, sizeof Ans);
memset (sumX, 0, sizeof sumX);
memset (sumY, 0, sizeof sumY);
}
int main () {
for (int t = Read(); t--; clr()) {
n = Read(), m = Read(), x = Read(), y = Read();
for (int i = 1; i <= n; i++) a[i] = Read(), b[i] = Read(), dtmp[++tot] = a[i], dtmp[++tot] = b[i];
for (int i = 1; i <= m; i++) a[i + n] = Read(), b[i + n] = Read(), dtmp[++tot] = a[i + n], dtmp[++tot] = b[i + n];
sort (dtmp + 1, dtmp + 1 + tot);
tot = unique (dtmp + 1, dtmp + 1 + tot) - dtmp - 1;
for (int i = 1; i <= n + m; i++) {
a[i] = lower_bound(dtmp + 1, dtmp + 1 + tot, a[i]) - dtmp;
b[i] = lower_bound(dtmp + 1, dtmp + 1 + tot, b[i]) - dtmp;
if (i <= n) sumX[a[i]]++, sumX[b[i]]--;
else sumY[a[i]]++, sumY[b[i]]--;
st[a[i]].emplace_back(i);
en[b[i]].emplace_back(i);
}
for (int i = n + m; i >= n + 1; i--) {
add_edge(a[i], b[i], 1);
id[i] = G[a[i]].size() - 1;
}
bool flag = 1;
for (int i = 1; i <= tot; i++) {
sumX[i] += sumX[i - 1], sumY[i] += sumY[i - 1];
if (i < tot)add_edge(i, i + 1, min(y, x + y - sumX[i] - sumY[i]));
if (sumX[i] > x || x + y - (sumX[i] + sumY[i]) < 0) {
puts("NO"); flag = 0; break;
}
}
if (!flag) continue;
nf.S = tot + 2, nf.T = nf.S + 1;
add_edge(nf.S, 1, y);
add_edge(tot, nf.T, nf.inf);
if(nf.dinic() != y) { puts("NO"); continue; }
puts("YES");
int topX = 0, topY = 0;
for (int i = 1; i <= x; i++) stX[++topX] = i;
for (int i = x + 1; i <= x + y; i++) stY[++topY] = i;
for (int i = 1; i <= tot; i++) {
for (int j : en[i]) {
if (Ans[j] <= x) stX[++topX] = Ans[j];
else stY[++topY] = Ans[j];
}
for (int j : st[i]) {
if (j <= n || G[a[j]][id[j]].w) Ans[j] = stX[topX--];
else Ans[j] = stY[topY--];
}
}
for (int i = 1; i <= n + m; i++) printf ("%d ", Ans[i]); putchar(10);
}
return 0;
}
}
int main () {
// freopen(".in", "r", stdin);
// freopen("1.out", "w", stdout);
Main::main();
return 0;
}
```