UVa 13008 Exposing Corruption

题目描述

在 $\text{Nlognia}$ 国家，中央委员会由许多议员组成。政治体系是二元的，每个议员属于两个政党之一： $\text{Deadly Serious Party}$ （ $\text{DSP }$）和 $\text{Party! Party! Party}$ （ $\text{PPP}$ ）。爱德华是一名调查记者，他发现议员们是腐败的：如果给予一定数量的 $\text{Nlognmoney}$ ，他们就会改变政党。每个议员都有自己的特定价格，但每个人都有价格。此外，某些议员之间存在敌对关系。敌对议员绝不会接受属于同一个政党。

爱德华有一笔预算，希望用它让一些议员改变政党，从而为调查收集证据。在此过程中，他必须尊重敌对关系：在所有接受金钱的议员改变政党后，敌对议员必须分属不同的政党。

爱德华希望造成最大的影响。对于每个测试用例，需要回答两个问题：

输入格式

每个测试用例的格式如下：

• 第一行：四个整数 $D$, $P$, $R$, $B$ ，分别表示初始属于 $\text{DSP}$ 的议员数量（ $1\le D\le 100$ ）、初始属于 $\text{PPP}$ 的议员数量（ $1\le P\le 100$ ）、敌对关系数量（ $1\le R\le 2000$ ）和预算（ $1\le B\le 10^4$ ）。
• 第二行： $D$ 个整数 $S_1,S_2,\dots ,S_D$ ，表示 $\text{DSP}$ 议员 $i$ 改变政党所需的价格（ $1\le S_i\le 100$ ）。
• 第三行： $P$ 个整数 $T_1,T_2,\dots ,T_P$ ，表示 $\text{PPP}$ 议员 $j$ 改变政党所需的价格（ $1\le T_j\le 100$ ）。
• 接下来 $R$ 行：每行两个整数 $X$ 和 $Y$ ，表示 $\text{DSP}$ 议员 $X$ 和 $\text{PPP}$ 议员 $Y$ 是敌对的（ $1\le X\le D$, $1\le Y\le P$ ）。

输出格式

对每个测试用例，输出一行两个整数：最大 $\text{DSP}$ 人数和最大 $\text{PPP}$ 人数。

题目分析

核心问题

本题可以抽象为一个图论+动态规划（背包） 问题：

关键观察

由于敌对关系只存在于不同初始党派的议员之间，整个图由若干个连通分量组成。在每个连通分量内部，一旦确定了某个议员的最终党派，由于敌对关系的传递性，整个分量的最终分配方案就确定了（二分图染色）。

对于每个连通分量，我们有两种可能的分配方案：

• 方案 $A$ ：让分量中的第一个节点保持其初始党派。
• 方案 $B$ ：让分量中的第一个节点改变到对立党派。

每种方案都有对应的：

• 成本 ：需要支付给那些初始党派与最终党派不同的议员的价格总和。
• 收益 ：最终属于 $\text{DSP}$ 的人数 $d$ 和属于 $\text{PPP}$ 的人数 $p$ 。

问题转化

这样，原问题就转化为一个分组背包问题：

• 每个连通分量是一个“物品组”，有两种选择（方案 $A$ 或方案 $B$）。
• 背包容量是预算 $B$ 。
• 选择每个分量的方案，使得总成本不超过 $B$ ，并最大化总收益（ $\text{DSP}$ 人数或 $\text{PPP}$ 人数）。

我们需要分别求解两个背包问题：一个最大化 $\text{DSP}$ 人数，另一个最大化 $\text{PPP}$ 人数。

算法步骤

复杂度分析

• 节点数 $N=D+P\le 200$ ，边数 $R\le 2000$ 。
• 连通分量分解： $O(N+R)$ 。
• 对每个分量染色： $O(N+R)$ 。
• 背包 DP ： $O(C\times B)$ ，其中 $C$ 是连通分量个数（最多 $N$ ）， $B\le 10^4$ 。
• 总复杂度在可接受范围内。

代码实现

// Exposing Corruption
// UVa ID: 13008
// Verdict: Accepted
// Submission Date: 2026-01-23
// UVa Run Time: 0.040s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 210;
const int MAXB = 10010;
vector<int> graph[MAXN];
int priceD[MAXN], priceP[MAXN], D, P, R, B;
bool visited[MAXN];

struct Comp {
int c0, d0, p0, c1, d1, p1;
};

vector<Comp> comps;

void dfs(int u, vector<int>& nodes) {
visited[u] = true;
nodes.push_back(u);
for (int v : graph[u]) if (!visited[v]) dfs(v, nodes);
}

void build() {
fill(visited, visited + MAXN, false);
comps.clear();
for (int i = 1; i <= D + P; ++i) if (!visited[i]) {
vector<int> nodes;
dfs(i, nodes);

// BFS染色
vector<int> color(nodes.size(), –1);
color[0] = 0;
queue<int> q; q.push(0);
while (!q.empty()) {
int idx = q.front(); q.pop();
int u = nodes[idx];
for (int v : graph[u]) {
auto it = find(nodes.begin(), nodes.end(), v);
if (it == nodes.end()) continue;
int vIdx = it – nodes.begin();
if (color[vIdx] == –1) color[vIdx] = 1 – color[idx], q.push(vIdx);
}
}

// 计算两种方案
Comp comp = {0, 0, 0, 0, 0, 0};
for (int j = 0; j < nodes.size(); ++j) {
int node = nodes[j], init = (node <= D) ? 0 : 1;
int final0 = color[j], final1 = 1 – final0;

// 方案0
if (init == 0) {
if (final0 == 0) comp.d0++;
else comp.p0++, comp.c0 += priceD[node];
} else {
if (final0 == 0) comp.d0++, comp.c0 += priceP[node];
else comp.p0++;
}

// 方案1
if (init == 0) {
if (final1 == 0) comp.d1++;
else comp.p1++, comp.c1 += priceD[node];
} else {
if (final1 == 0) comp.d1++, comp.c1 += priceP[node];
else comp.p1++;
}
}
comps.push_back(comp);
}
}

int solve(bool forDSP) {
vector<int> dp(B + 1, 0);
for (const Comp& c : comps) for (int b = B; b >= 0; —b) {
if (b >= c.c0) dp[b] = max(dp[b], dp[b – c.c0] + (forDSP ? c.d0 : c.p0));
if (b >= c.c1) dp[b] = max(dp[b], dp[b – c.c1] + (forDSP ? c.d1 : c.p1));
}
return dp[B];
}

int main() {
while (cin >> D >> P >> R >> B) {
for (int i = 0; i < MAXN; ++i) graph[i].clear();
for (int i = 1; i <= D; ++i) cin >> priceD[i];
for (int j = 1; j <= P; ++j) cin >> priceP[j + D];
for (int i = 0; i < R; ++i) {
int x, y; cin >> x >> y;
graph[x].push_back(y + D);
graph[y + D].push_back(x);
}
build();
cout << solve(true) << " " << solve(false) << endl;
}
return 0;
}

总结

本题是一道综合性较强的题目，需要结合图论（二分图染色）和动态规划（背包问题）进行求解。关键是将原问题分解为连通分量，并识别出每个分量只有两种可能的分配方案。通过将问题转化为分组背包，可以高效地求解最大人数。算法复杂度合理，能够处理题目给定的数据范围。