You are given a tree...
树上dp #状态压缩 #随机优化
题目描述
给定一棵带边权的树 \(T=(V,E)\)，其中 \(|V|=n\)，顶点编号为 \(1, 2, \dots, n\)，每个顶点 \(i\) 有一个权值 \(a_i\)。
你需要选择一个顶点子集 \(S \subseteq V\)，满足 \(S\) 中最多包含 \(k\) 个顶点，并且这些顶点的权值 \(a_i\) 互不相同。目标是最大化被“覆盖”的边的权重之和。一条边 \(e\) 被“覆盖”当且仅当存在 \(u, v \in S\)，使得 \(e\) 位于 \(u\) 到 \(v\) 的唯一路径上。
输入描述
第一行包含两个整数 \(n, k\) \((1 \le n \le 5000, 2 \le k \le 5)\)，分别表示树的大小和子集 \(S\) 的最大大小。
第二行包含 \(n\) 个整数 \(a_1, a_2, \dots, a_n\) \((1 \le a_i \le n)\)，表示每个顶点的权值。
接下来 \(n-1\) 行，每行包含三个整数 \(u, v, w\) \((1 \le u, v \le n, -10^9 \le w \le 10^9)\)，表示树中有一条连接 \(u\) 和 \(v\)、权重为 \(w\) 的边。
输出描述
输出一行一个整数，表示被“覆盖”边的权重之和的最大值。
思路
先将所有权值进行状态压缩，第\(pos\)位为1代表当前状态包含权值\(a_{pos}\)
很显然这是一个树上dp：
- 状态表示：
- \(dp[u][mk]\)表示以\(u\)为根的子树内，权值选择状态为\(mk\)的最大边权之和
- 状态转移：
- 设当前回溯状态为\(u\xrightarrow{w}son\)
- \(mk\)从1遍历至\(one\)，\(dp[son][mk]+=w\)
- 子树状态由“以\(son\)为根节点的子树中状态为\(mk\)的最大边权之和”变为“以\(son\)为根节点的子树中状态为\(mk\)的最大边权之和加上当前边权”
- 枚举\(u\)已经处理完的子树的状态\(S\)
- 枚举\(S\)的子集\(T\)
- \(dp[u][S]=max\{ dp[u][S],dp[u][S\oplus T]+dp[son][T] \}\)
- 若\(S\oplus T> 0\)，则已经处理完的树和\(son\)子树都非空，可以更新答案：\(ans=max\{ ans,dp[u][S\oplus T]+dp[son][T] \}\)
然而，一共有\(n\)个权值，若要进行状态压缩则一共有\(2^{n}\)个状态，在\(n=5000\)的时候明显不行
但是，注意到可以选择的点数\(k\leq 5\)，若选定了\(s\)种权值，那么仅有\(2^{s}\)种状态
因此采用随机优化：
将\(n\)个权值随机分成\(k\leq 5\)类，每一种权值都属于5类中的其中一类
假设最优的答案是由\(\{ s_{1},s_{2},s_{3},s_{4},s_{5} \}\)这5种权值构成的：
- 当这5种权值恰好分到的是不同的5类时，将类编号看作新的权值，由于其他不属于这5种权值的点对答案没有贡献，跑出来的答案必定是最优答案
- 当这5种权值分到的并不刚好是这5类时，会把其中某几个权值视作同一类，那么跑出来的答案将会偏小
由于无论怎么分类，跑出来的答案\(ans'\)永远小于等于最优答案\(ans\)，所以可以跑很多次之后对答案取最大值
对于所有的随机分类方案，能够跑出最优答案的方案便是\(\{ s_{1},s_{2},s_{3},s_{4},s_{5} \}\)分到的恰好是不同类，因此可以计算这个概率：
- 这5个数随便分类的方案数为\(k^{5}\)
- 这5个数分到不同的类中的方案数为\(k\cdot (k-1)\cdot(k-2)\cdot(k-3)\cdot(k-4)\)
- 最终概率为\(\frac{k\cdot (k-1)\cdot(k-2)\cdot(k-3)\cdot(k-4)}{k^{5}}\geq \frac{24}{625}\)
随机实验\(T\)次，只需要有一次是最优答案即可ac，概率为\(1-\left( 1- \frac{24}{625} \right)^{T}\)
当\(T=200\)时，概率为\(0.9954\)，wa变成了小概率事件
因此将所有类\(col[5]\)进行状态压缩，第\(pos\)位为1代表当前状态包含类\(col_{pos}\)
跑上述树上dp即可
代码
#include <iostream>
#include <vector>
#include <unordered_map>
#include<map>
#include<unordered_set>
#include <set>
#include<algorithm>
#include <bits/chrono.h>
#include <random>
using namespace std;
const double eps = 1e-6;
#define ll long long
#define int ll
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define see(stl) for(auto&ele:stl)cout<<ele<<" ";cout<<'\n';
#pragma GCC optimize(3, "Ofast", "inline")
const int N = 5005;
int a[N], col[N];const int inf = 1e18;vector<pair<int, int>>e[N];//{w,next}
int dp[N][1<<5];
void chmax(int& x, int y) { x = max(x, y); }int k, ans = 0, one;void dfs(int u, int fa) {dp[u][0] = 0;dp[u][1 << col[a[u]]] = 0;for (auto [w, son] : e[u]) {if (son == fa)continue;dfs(son, u);rep(S, 1, one) {dp[son][S] += w;}per(S, one, 0) {for (int T = S;T;T = (T - 1) & S) {chmax(dp[u][S], dp[u][S ^ T] + dp[son][T]);if (S ^ T)chmax(ans, dp[u][S ^ T] + dp[son][T]);}}}
}void solve() {int n;cin >> n >> k;one = (1 << k) - 1;unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();mt19937 rand_num(seed);uniform_int_distribution<int> dist(0, k - 1);rep(i, 1, n)cin >> a[i];rep(i, 1, n - 1) {int u, v, w;cin >> u >> v >> w;e[u].push_back({ w,v });e[v].push_back({ w,u });}rep(tim, 0, 200) {rep(i, 1, n) {rep(mk, 0, one)dp[i][mk] = -inf;}rep(i, 1, n)col[i] = dist(rand_num);dfs(1, 0);}cout << ans << '\n';
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);int t = 1;// cin >> t;while (t--)solve();return 0;
}
Reviewer Assignment
网络流 #网络流费用流 #图
题目描述
gispzjz 喜欢玩 DotA2，并且最近成为了 DotA2 社区中著名会议 SODA（DotA2 研讨会）的主席，该会议专注于与 DotA2 游戏策略设计和分析相关的研究主题。
现在，2023 年 DotA2 研讨会的论文征集截止日期已过，gispzjz 收到了大量的论文！幸运的是，SODA 会议也有许多审稿人，gispzjz 的工作是将论文分配给审稿人进行评审。然而，由于论文作者和审稿人之间可能存在利益冲突，每个审稿人只被允许评审特定的论文子集。同时，为了避免给每个审稿人分配过多工作，gispzjz 应该为每个审稿人恰好分配一篇论文，而每篇论文允许被多个审稿人评审，甚至不被任何审稿人评审。
作为会议主席，gispzjz 希望每篇论文都能得到公平的评审，因此他希望以如下方式将论文分配给审稿人：首先最大化至少被评审一次的论文数量，在此约束下，再最大化至少被评审两次的论文数量，然后在满足前两个约束的前提下，最大化至少被评审三次的论文数量，依此类推。当然 gispzjz 本可以轻易想出最优分配方案，但他刚刚去玩 DotA2 了，把这个问题留给了你。
输入描述
输入的第一行包含两个整数 \(n, m (1 \leq n, m \leq 400)\)，分别表示审稿人和论文的数量。
接下来是 \(n\) 行，每行包含一个长度为 \(m\) 的字符串，由 \(0\) 和 \(1\) 组成。其中第 \(i (1 \leq i \leq n)\) 个字符串的第 \(j (1 \leq j \leq m)\) 个字符为 \(1\) 表示第 \(i\) 位审稿人被允许评审第 \(j\) 篇论文，否则不允许。
输出描述
如果无法找到一种方式将论文分配给审稿人，使得每个审稿人恰好收到一篇论文，则在一行中输出 \(-1\)。否则，输出一行包含 \(n\) 个整数 \(a_1, a_2, \dots, a_n (1 \leq a_i \leq m)\)，表示在第 \(i\) 位审稿人被分配了第 \(a_i\) 篇论文的最优分配方案。如果存在多个最优分配方案，输出任意一个均视为正确。
思路
由于题干要求分层最大值，让人很容易联想到网络流最大流前提下最小费用
- \(S\to审稿人\)：容量为1，费用为0
- 每个审稿人只能审一篇文章，没有优先顺序之分
- \(审稿人\to论文\)：容量为1，费用为0
- 如果能够审就连边
- 同样每个审稿人只可以审一篇文章，但一篇文章可以被多个人审核
- \(论文\to T\)：容量为1，费用升序
- 让每篇论文向汇点连\(n\)条边，容量均为1，费用依次为\(1,2,\dots,n\)
- 这样建边可以使得一篇论文多一个审稿人的代价越来越高
- 最小费用最大流会在尽量让更多论文被人审理的前提下自动选择最便宜的流量路径
因此，令\(1\sim n\)为审稿人，\(n+1\sim n+m+1\)为论文，0为\(S\)，\(1+n+m\)为\(T\)建边
跑完网络流后，若最大流\(<n\)说明有审稿人没有论文可以审，输出-1
否则，遍历所有的审稿人，遍历所有审稿人所连的边，若当前边\(w==0\)，代表已经流满，其连接的论文即为当前审稿人所对应的论文
由于要多建很多题干没有提及的变，需要特别注意边集数组的大小
代码
#include<iostream>
#include<vector>
#include<unordered_map>
#include<map>
#include<unordered_set>
#include<string.h>
#include<algorithm>
#include<queue>using namespace std;
const double eps = 1e-6;
#define ll long long
//#define int ll
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define see(stl) for(auto&ele:stl)cout<<ele<<" ";cout<<'\n';
//#pragma GCC optimize(3, "Ofast", "inline")
//#define u128 __int128const int N = 4e2 + 5, inf = 1e9;
int n, m, s, t;
char a[N][N];
int h[N << 1], idx = 2;
struct E { int son, w, c, ne; }e[(N * N) << 3];
void add(int a, int b, int w, int c) {e[idx] = { b,w,c,h[a] };h[a] = idx++;
}
void ADD(int a, int b, int w, int c) {add(a, b, w, c);add(b, a, 0, -c);
}
bool vis[N << 1];
int mf[N << 1], pre[N << 1], d[N << 1];
bool spfa() {rep(i, 0, n + m + 1)vis[i] = 0, mf[i] = 0, d[i] = inf;deque<int>dq;dq.push_back(0);vis[s] = 1, mf[s] = inf, d[s] = 0;while (dq.size()) {int u = dq.front();dq.pop_front();vis[u] = 0;for (int i = h[u];i;i = e[i].ne) {auto [son, w, c, ne] = e[i];if (w && d[son] > d[u] + c) {d[son] = d[u] + c;mf[son] = min(w, mf[u]);pre[son] = i;if (!vis[son]) {dq.push_back(son);vis[son] = 1;}}}}return mf[t] > 0;
}
pair<int, int>EK() {int flow = 0, cost = 0;while (spfa()) {int p = n + m + 1;while (p != 0) {int i = pre[p];e[i].w -= mf[t];e[i ^ 1].w += mf[t];p = e[i ^ 1].son;}flow += mf[t];cost += mf[t] * d[t];}return { flow,cost };
}void solve() {idx = 2;cin >> n >> m;s = 0, t = n + m + 1;rep(i, 1, n) {rep(j, 1, m) {cin >> a[i][j];if (a[i][j] == '1') {ADD(i, n + j, 1, 0);}}}rep(i, 1, n)ADD(s, i, 1, 0);rep(i, n + 1, n + m) {rep(j, 1, n) {ADD(i, t, 1, j);}}pair<int, int>ans = EK();if (ans.first < n) {cout << -1 << '\n';return;}rep(u, 1, n) {for (int i = h[u];i;i = e[i].ne) {if (i & 1)continue;auto [son, w, c, ne] = e[i];if (!w && son > n && son <= n + m) {cout << son - n << " ";break;}}}
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);int t = 1;//cin >> t;while (t--)solve();return 0;
}