Codeforces 1525F 二分图最小点覆盖 + DP

题意

传送门 Codeforces 1525F Goblins And Gnomes

题解

若 DAG 的最小路径覆盖数小于等于哥布林数，则必败。DAG 的最小路径覆盖是一个经典问题，可以转换为求解拆点二分图的最大匹配。只删除图中某个节点的出边或入边等价于删除二分图上的某个节点，最大化收益则需要删除的点数尽可能小，那删除二分图最大匹配的必经点可以满足要求。若必经点存在，需要 $O(n)$ 依次删除节点，$O(n^3)$ 枚举节点判断是否将其删除后最大匹配数减少一。这样处理 $O(n^4)$，实际上求解删除节点序列可以做到 $O(n^3)$。

二分图的最小点覆盖等于最大匹配。以任意次序删除二分图的最小点覆盖可以发现，最大匹配数依次减少一。那么问题中删除的点集就是最小点覆盖的某个子集。

二分图最小点覆盖可以 $O(nm)$ 求解。最后 $DP$ 依次枚举一波攻击删除的点数即可。总时间复杂度 $O(n^3)$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int MAXN = 105;
int N, M, K;
vector<int> G[MAXN];
int X[MAXN], Y[MAXN];
bool used[MAXN];
int match[MAXN], pre[MAXN][MAXN];
ll dp[MAXN][MAXN];
bool dfs(int v)
{
used[v] = 1;
for (int u : G[v])
{
int w = match[u];
if (w == -1 || (!used[w] && dfs(w)))
{
match[u] = v, match[v] = u;
return 1;
}
}
return 0;
}
void find(int v)
{
used[v] = 1;
for (int u : G[v])
{
used[u] = 1;
int w = match[u];
if (!used[w])
find(w);
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> N >> M >> K;
for (int i = 0; i < M; ++i)
{
int u, v;
cin >> u >> v;
--u, --v;
G[u].push_back(N + v);
}
for (int i = 0; i < K; ++i)
cin >> X[i] >> Y[i];
memset(match, -1, sizeof(match));
int s = 0;
for (int i = 0; i < N; ++i)
memset(used, 0, sizeof(used)), s += dfs(i);
memset(used, 0, sizeof(used));
for (int i = 0; i < N; ++i)
if (match[i] == -1)
find(i);
vector<int> vs;
for (int i = 0; i < N; ++i)
if (!used[i])
vs.push_back(i + 1);
for (int i = 0; i < N; ++i)
if (used[N + i])
vs.push_back(-(i + 1));
assert(vs.size() == s);
memset(dp, 0xc0, sizeof(dp));
memset(pre, -1, sizeof(pre));
dp[0][s] = 0;
for (int i = 0; i < K; ++i)
for (int j = 0; j <= s; ++j)
for (int k = min(j, N - (i + 2)); k >= 0; --k)
{
ll t = max(0ll, X[i] - (ll)(j - k) * Y[i]);
if (dp[i + 1][k] < dp[i][j] + t)
dp[i + 1][k] = dp[i][j] + t, pre[i + 1][k] = j;
}
int num = -1;
for (int i = N - (K + 1); i >= 0; --i)
if (num == -1 || dp[K][i] > dp[K][num])
num = i;
vector<vector<int>> act(K);
for (int i = K, j = num; i; --i)
{
for (int k = j; k < pre[i][j]; ++k)
act[i - 1].push_back(vs[k]);
j = pre[i][j];
}
int sum = 0;
for (int i = 0; i < K; ++i)
sum += act[i].size() + 1;
cout << sum << 'n';
for (int i = 0; i < K; ++i)
{
for (int a : act[i])
cout << a << ' ';
cout << "0 ";
}
return 0;
}

最后

以上就是幸福发带为你收集整理的Codeforces 1525F 二分图最小点覆盖 + DP的全部内容，希望文章能够帮你解决Codeforces 1525F 二分图最小点覆盖 + DP所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。