Rainbow Bracket Sequence

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;
	} else
		cout << -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 , 感谢他的图和教导。