The 2024 ICPC Asia East Continent Online Contest (I)
题意
构造长度为 \(2n\) 的合法括号序列。
对于每个左括号在的位置 \(i\), 都有颜色 \(c_i\) 和价值 \(v_i\)。
左括号颜色视为所在位置颜色, 价值同理。
对于每个颜色,满足左括号为该颜色的个数 \(\geq l_i\)。
求满足以上条件下,最大左括号的价值和。
\(n \leq 100, m \leq n, v_i \leq 10^9\)。
做法
是费用流,关键在于建模。
- 保证合法括号序列
首先构建点 \(1 \dots 2n\) 表示所有括号序列。
把原点 \(S\) 连向所有奇数点,即 \(S \to 1, S\to 3, \dots, S \to 2n - 1\)。
流量,边权 为 \((1, 0)\), 即表示左括号在这些点。
同时,对 \(i + 1 \to i\), 连 \((+\infty, 0)\), 表示左括号可以向左移动。
可以发现, 这样构造出来的括号序列总是合法的, 总能保证左右括号匹配且任意前缀左括号个数大于等于右括号个数。
- 颜色限制
首先, 每个位置 \(i\) 连向对应颜色 \(c_i\), 边权为 \(-v_i\), 流量为 \(1\)。
为了保证颜色 \(i\) 有 \(l_i\) 个, 连 \(c_i \to T\) 时, 流量为 \(l_i\), 边权为 \(-\infty\),(可以是极小的数 \(-10^{13}\)) 表示一定要选。
对于超过 \(l_i\) 的部分,连 \(c_i \to T\) 的 \((\infty, 0)\) 的边, 表示可以选。
- 跑最小费用最大流即可
求得 \(\lfloor\frac{\text{mincost}}{-10^{13}}\rfloor = \sum l_i\), 即有解,
最后的答案为 \(\text{mincost} \mod (-10^{13})\)。
code
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 10100;
const ll INF = 1e13; int n, m, s, t;
int col[N], val[N], l[N]; struct edge {int v, len, next;ll w;
} e[N];
int cnt;
int first[N], cur[N]; void add(int u, int v, int len, ll w) {++ cnt;e[cnt].v = v;e[cnt].len = len; e[cnt].w = w; e[cnt].next = first[u];first[u] = cnt;
}
void Add(int u, int v, int len, ll w) {add(u, v, len, w); add(v, u, 0, -w);
}
void init() {cnt = 1; s = 2 * n + m + 1, t = 2 * n + m + 2; for (int i = 1; i <= t; i ++)first[i] = 0;
}bool vis[N];
ll dis[N];
bool bfs() {memcpy(cur, first, sizeof(first)); for (int i = 1; i <= t; i ++)vis[i] = 0, dis[i] = INF;queue<int> q; q.push(s); dis[s] = 0; while (!q.empty()) {int u = q.front(); q.pop();vis[u] = 0; for (int i = first[u]; i; i = e[i].next) {int v = e[i].v, len = e[i].len;ll w = e[i].w; if (!len || dis[v] <= dis[u] + w) continue;dis[v] = dis[u] + w;if (!vis[v]) {q.push(v),vis[v] = 1; }}}return dis[t] != INF;
}
ll cost;
int dfs(int u, int flow) {if (u == t) {return flow; }int ans = 0; vis[u] = 1;for (int &i = cur[u]; i; i = e[i].next) {int v = e[i].v, len = e[i].len; ll w = e[i].w; if (vis[v] || dis[v] != dis[u] + w || !len) continue; int out = dfs(v, min(len, flow));if (out) {ans += out; cost += 1ll * out * w; e[i].len -= out;e[i ^ 1].len += out; flow -= out; } }return ans;
}
ll dinic() {ll ans = 0; while (bfs()) {cost = 0; dfs(s, 0x7fffffff);ans += cost;}return ans;
}void solve() {cin >> n >> m; init(); int suml = 0; for (int i = 1; i <= m; i ++)cin >> l[i], suml += l[i];for (int i = 1; i <= 2 * n; i ++) cin >> col[i]; for (int i = 1; i <= 2 * n; i ++)cin >> val[i]; for (int i = 1; i <= 2 * n; i += 2)Add(s, i, 1, 0); for (int i = 1; i <= 2 * n - 1; i ++) Add(i + 1, i, 0x7fffffff, 0); for (int i = 1; i <= 2 * n; i ++)Add(i, 2 * n + col[i], 1, - val[i]); for (int i = 1; i <= m; i ++) {Add(2 * n + i, t, l[i], -INF);Add(2 * n + i, t, 0x7fffffff, 0); }ll cost = dinic();if (cost / (-INF) == suml) {cout << (-cost) % INF << endl;} elsecout << -1 << endl;
} int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0); int T;cin >>T;while (T --)solve(); return 0;
}
最后 %%%klii , 感谢他的图和教导。