题目描述在Nlognia\texttt{Nlognia}Nlognia国家中央委员会由许多议员组成。政治体系是二元的每个议员属于两个政党之一Deadly Serious Party\texttt{Deadly Serious Party}Deadly Serious PartyDSP \texttt{DSP }DSP和Party! Party! Party\texttt{Party! Party! Party}Party! Party! PartyPPP\texttt{PPP}PPP。爱德华是一名调查记者他发现议员们是腐败的如果给予一定数量的Nlognmoney\texttt{Nlognmoney}Nlognmoney他们就会改变政党。每个议员都有自己的特定价格但每个人都有价格。此外某些议员之间存在敌对关系。敌对议员绝不会接受属于同一个政党。爱德华有一笔预算希望用它让一些议员改变政党从而为调查收集证据。在此过程中他必须尊重敌对关系在所有接受金钱的议员改变政党后敌对议员必须分属不同的政党。爱德华希望造成最大的影响。对于每个测试用例需要回答两个问题使用最多全部预算可以使得最终属于DSP\texttt{DSP}DSP的议员的最大数量是多少同样条件下可以使得最终属于PPP\texttt{PPP}PPP的议员的最大数量是多少输入格式每个测试用例的格式如下第一行四个整数DDD,PPP,RRR,BBB分别表示初始属于DSP\texttt{DSP}DSP的议员数量1≤D≤1001 \leq D \leq 1001≤D≤100、初始属于PPP\texttt{PPP}PPP的议员数量1≤P≤1001 \leq P \leq 1001≤P≤100、敌对关系数量1≤R≤20001 \leq R \leq 20001≤R≤2000和预算1≤B≤1041 \leq B \leq 10^{4}1≤B≤104。第二行DDD个整数S1,S2,...,SDS_1, S_2, ..., S_DS1,S2,...,SD表示DSP\texttt{DSP}DSP议员iii改变政党所需的价格1≤Si≤1001 \leq S_i \leq 1001≤Si≤100。第三行PPP个整数T1,T2,...,TPT_1, T_2, ..., T_PT1,T2,...,TP表示PPP\texttt{PPP}PPP议员jjj改变政党所需的价格1≤Tj≤1001 \leq T_j \leq 1001≤Tj≤100。接下来RRR行每行两个整数XXX和YYY表示DSP\texttt{DSP}DSP议员XXX和PPP\texttt{PPP}PPP议员YYY是敌对的1≤X≤D1 \leq X \leq D1≤X≤D,1≤Y≤P1 \leq Y \leq P1≤Y≤P。输出格式对每个测试用例输出一行两个整数最大DSP\texttt{DSP}DSP人数和最大PPP\texttt{PPP}PPP人数。题目分析核心问题本题可以抽象为一个图论动态规划背包问题图模型议员构成一个二分图左侧是DSP\texttt{DSP}DSP议员编号1..D1..D1..D右侧是PPP\texttt{PPP}PPP议员编号D1..DPD1..DPD1..DP。敌对关系是连接左右两侧的边。约束条件敌对议员最终必须属于不同政党。操作可以支付一定价格让某个议员改变政党从DSP\texttt{DSP}DSP变为PPP\texttt{PPP}PPP或反之。目标在不超过预算BBB的前提下最大化最终属于某个政党的人数。关键观察由于敌对关系只存在于不同初始党派的议员之间整个图由若干个连通分量组成。在每个连通分量内部一旦确定了某个议员的最终党派由于敌对关系的传递性整个分量的最终分配方案就确定了二分图染色。对于每个连通分量我们有两种可能的分配方案方案AAA让分量中的第一个节点保持其初始党派。方案BBB让分量中的第一个节点改变到对立党派。每种方案都有对应的成本需要支付给那些初始党派与最终党派不同的议员的价格总和。收益最终属于DSP\texttt{DSP}DSP的人数ddd和属于PPP\texttt{PPP}PPP的人数ppp。问题转化这样原问题就转化为一个分组背包问题每个连通分量是一个“物品组”有两种选择方案AAA或方案BBB。背包容量是预算BBB。选择每个分量的方案使得总成本不超过BBB并最大化总收益DSP\texttt{DSP}DSP人数或PPP\texttt{PPP}PPP人数。我们需要分别求解两个背包问题一个最大化DSP\texttt{DSP}DSP人数另一个最大化PPP\texttt{PPP}PPP人数。算法步骤建图与连通分量分解将DSP\texttt{DSP}DSP议员编号为1..D1..D1..DPPP\texttt{PPP}PPP议员编号为D1..DPD1..DPD1..DP。根据敌对关系建立无向图。使用DFS\texttt{DFS}DFS或BFS\texttt{BFS}BFS找出所有连通分量。对每个连通分量计算两种方案通过二分图染色确定分量内节点的颜色分配000表示最终属于DSP\texttt{DSP}DSP111表示最终属于PPP\texttt{PPP}PPP。方案AAA假设第一个节点颜色为000如果它是DSP\texttt{DSP}DSP或111如果它是PPP\texttt{PPP}PPP。方案BBB将方案AAA的颜色取反。分别计算两种方案的成本、最终DSP\texttt{DSP}DSP人数和PPP\texttt{PPP}PPP人数。动态规划背包定义dp[b]dp[b]dp[b]表示使用预算bbb时能获得的最大人数。对于每个连通分量从BBB向下遍历更新dpdpdpdp[b]max(dp[b],dp[b−costA]gainA)dp[b] \max(dp[b], dp[b-cost_A] gain_A)dp[b]max(dp[b],dp[b−costA]gainA)dp[b]max(dp[b],dp[b−costB]gainB)dp[b] \max(dp[b], dp[b-cost_B] gain_B)dp[b]max(dp[b],dp[b−costB]gainB)分别计算最大化DSP\texttt{DSP}DSP和PPP\texttt{PPP}PPP的情况。复杂度分析节点数NDP≤200N D P \leq 200NDP≤200边数R≤2000R \leq 2000R≤2000。连通分量分解O(NR)O(N R)O(NR)。对每个分量染色O(NR)O(N R)O(NR)。背包 DP O(C×B)O(C \times B)O(C×B)其中CCC是连通分量个数最多NNNB≤104B \leq 10^4B≤104。总复杂度在可接受范围内。代码实现// Exposing Corruption// UVa ID: 13008// Verdict: Accepted// Submission Date: 2026-01-23// UVa Run Time: 0.040s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXN210;constintMAXB10010;vectorintgraph[MAXN];intpriceD[MAXN],priceP[MAXN],D,P,R,B;boolvisited[MAXN];structComp{intc0,d0,p0,c1,d1,p1;};vectorCompcomps;voiddfs(intu,vectorintnodes){visited[u]true;nodes.push_back(u);for(intv:graph[u])if(!visited[v])dfs(v,nodes);}voidbuild(){fill(visited,visitedMAXN,false);comps.clear();for(inti1;iDP;i)if(!visited[i]){vectorintnodes;dfs(i,nodes);// BFS染色vectorintcolor(nodes.size(),-1);color[0]0;queueintq;q.push(0);while(!q.empty()){intidxq.front();q.pop();intunodes[idx];for(intv:graph[u]){autoitfind(nodes.begin(),nodes.end(),v);if(itnodes.end())continue;intvIdxit-nodes.begin();if(color[vIdx]-1)color[vIdx]1-color[idx],q.push(vIdx);}}// 计算两种方案Comp comp{0,0,0,0,0,0};for(intj0;jnodes.size();j){intnodenodes[j],init(nodeD)?0:1;intfinal0color[j],final11-final0;// 方案0if(init0){if(final00)comp.d0;elsecomp.p0,comp.c0priceD[node];}else{if(final00)comp.d0,comp.c0priceP[node];elsecomp.p0;}// 方案1if(init0){if(final10)comp.d1;elsecomp.p1,comp.c1priceD[node];}else{if(final10)comp.d1,comp.c1priceP[node];elsecomp.p1;}}comps.push_back(comp);}}intsolve(boolforDSP){vectorintdp(B1,0);for(constCompc:comps)for(intbB;b0;--b){if(bc.c0)dp[b]max(dp[b],dp[b-c.c0](forDSP?c.d0:c.p0));if(bc.c1)dp[b]max(dp[b],dp[b-c.c1](forDSP?c.d1:c.p1));}returndp[B];}intmain(){while(cinDPRB){for(inti0;iMAXN;i)graph[i].clear();for(inti1;iD;i)cinpriceD[i];for(intj1;jP;j)cinpriceP[jD];for(inti0;iR;i){intx,y;cinxy;graph[x].push_back(yD);graph[yD].push_back(x);}build();coutsolve(true) solve(false)endl;}return0;}总结本题是一道综合性较强的题目需要结合图论二分图染色和动态规划背包问题进行求解。关键是将原问题分解为连通分量并识别出每个分量只有两种可能的分配方案。通过将问题转化为分组背包可以高效地求解最大人数。算法复杂度合理能够处理题目给定的数据范围。
UVa 13008 Exposing Corruption
题目描述在Nlognia\texttt{Nlognia}Nlognia国家中央委员会由许多议员组成。政治体系是二元的每个议员属于两个政党之一Deadly Serious Party\texttt{Deadly Serious Party}Deadly Serious PartyDSP \texttt{DSP }DSP和Party! Party! Party\texttt{Party! Party! Party}Party! Party! PartyPPP\texttt{PPP}PPP。爱德华是一名调查记者他发现议员们是腐败的如果给予一定数量的Nlognmoney\texttt{Nlognmoney}Nlognmoney他们就会改变政党。每个议员都有自己的特定价格但每个人都有价格。此外某些议员之间存在敌对关系。敌对议员绝不会接受属于同一个政党。爱德华有一笔预算希望用它让一些议员改变政党从而为调查收集证据。在此过程中他必须尊重敌对关系在所有接受金钱的议员改变政党后敌对议员必须分属不同的政党。爱德华希望造成最大的影响。对于每个测试用例需要回答两个问题使用最多全部预算可以使得最终属于DSP\texttt{DSP}DSP的议员的最大数量是多少同样条件下可以使得最终属于PPP\texttt{PPP}PPP的议员的最大数量是多少输入格式每个测试用例的格式如下第一行四个整数DDD,PPP,RRR,BBB分别表示初始属于DSP\texttt{DSP}DSP的议员数量1≤D≤1001 \leq D \leq 1001≤D≤100、初始属于PPP\texttt{PPP}PPP的议员数量1≤P≤1001 \leq P \leq 1001≤P≤100、敌对关系数量1≤R≤20001 \leq R \leq 20001≤R≤2000和预算1≤B≤1041 \leq B \leq 10^{4}1≤B≤104。第二行DDD个整数S1,S2,...,SDS_1, S_2, ..., S_DS1,S2,...,SD表示DSP\texttt{DSP}DSP议员iii改变政党所需的价格1≤Si≤1001 \leq S_i \leq 1001≤Si≤100。第三行PPP个整数T1,T2,...,TPT_1, T_2, ..., T_PT1,T2,...,TP表示PPP\texttt{PPP}PPP议员jjj改变政党所需的价格1≤Tj≤1001 \leq T_j \leq 1001≤Tj≤100。接下来RRR行每行两个整数XXX和YYY表示DSP\texttt{DSP}DSP议员XXX和PPP\texttt{PPP}PPP议员YYY是敌对的1≤X≤D1 \leq X \leq D1≤X≤D,1≤Y≤P1 \leq Y \leq P1≤Y≤P。输出格式对每个测试用例输出一行两个整数最大DSP\texttt{DSP}DSP人数和最大PPP\texttt{PPP}PPP人数。题目分析核心问题本题可以抽象为一个图论动态规划背包问题图模型议员构成一个二分图左侧是DSP\texttt{DSP}DSP议员编号1..D1..D1..D右侧是PPP\texttt{PPP}PPP议员编号D1..DPD1..DPD1..DP。敌对关系是连接左右两侧的边。约束条件敌对议员最终必须属于不同政党。操作可以支付一定价格让某个议员改变政党从DSP\texttt{DSP}DSP变为PPP\texttt{PPP}PPP或反之。目标在不超过预算BBB的前提下最大化最终属于某个政党的人数。关键观察由于敌对关系只存在于不同初始党派的议员之间整个图由若干个连通分量组成。在每个连通分量内部一旦确定了某个议员的最终党派由于敌对关系的传递性整个分量的最终分配方案就确定了二分图染色。对于每个连通分量我们有两种可能的分配方案方案AAA让分量中的第一个节点保持其初始党派。方案BBB让分量中的第一个节点改变到对立党派。每种方案都有对应的成本需要支付给那些初始党派与最终党派不同的议员的价格总和。收益最终属于DSP\texttt{DSP}DSP的人数ddd和属于PPP\texttt{PPP}PPP的人数ppp。问题转化这样原问题就转化为一个分组背包问题每个连通分量是一个“物品组”有两种选择方案AAA或方案BBB。背包容量是预算BBB。选择每个分量的方案使得总成本不超过BBB并最大化总收益DSP\texttt{DSP}DSP人数或PPP\texttt{PPP}PPP人数。我们需要分别求解两个背包问题一个最大化DSP\texttt{DSP}DSP人数另一个最大化PPP\texttt{PPP}PPP人数。算法步骤建图与连通分量分解将DSP\texttt{DSP}DSP议员编号为1..D1..D1..DPPP\texttt{PPP}PPP议员编号为D1..DPD1..DPD1..DP。根据敌对关系建立无向图。使用DFS\texttt{DFS}DFS或BFS\texttt{BFS}BFS找出所有连通分量。对每个连通分量计算两种方案通过二分图染色确定分量内节点的颜色分配000表示最终属于DSP\texttt{DSP}DSP111表示最终属于PPP\texttt{PPP}PPP。方案AAA假设第一个节点颜色为000如果它是DSP\texttt{DSP}DSP或111如果它是PPP\texttt{PPP}PPP。方案BBB将方案AAA的颜色取反。分别计算两种方案的成本、最终DSP\texttt{DSP}DSP人数和PPP\texttt{PPP}PPP人数。动态规划背包定义dp[b]dp[b]dp[b]表示使用预算bbb时能获得的最大人数。对于每个连通分量从BBB向下遍历更新dpdpdpdp[b]max(dp[b],dp[b−costA]gainA)dp[b] \max(dp[b], dp[b-cost_A] gain_A)dp[b]max(dp[b],dp[b−costA]gainA)dp[b]max(dp[b],dp[b−costB]gainB)dp[b] \max(dp[b], dp[b-cost_B] gain_B)dp[b]max(dp[b],dp[b−costB]gainB)分别计算最大化DSP\texttt{DSP}DSP和PPP\texttt{PPP}PPP的情况。复杂度分析节点数NDP≤200N D P \leq 200NDP≤200边数R≤2000R \leq 2000R≤2000。连通分量分解O(NR)O(N R)O(NR)。对每个分量染色O(NR)O(N R)O(NR)。背包 DP O(C×B)O(C \times B)O(C×B)其中CCC是连通分量个数最多NNNB≤104B \leq 10^4B≤104。总复杂度在可接受范围内。代码实现// Exposing Corruption// UVa ID: 13008// Verdict: Accepted// Submission Date: 2026-01-23// UVa Run Time: 0.040s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXN210;constintMAXB10010;vectorintgraph[MAXN];intpriceD[MAXN],priceP[MAXN],D,P,R,B;boolvisited[MAXN];structComp{intc0,d0,p0,c1,d1,p1;};vectorCompcomps;voiddfs(intu,vectorintnodes){visited[u]true;nodes.push_back(u);for(intv:graph[u])if(!visited[v])dfs(v,nodes);}voidbuild(){fill(visited,visitedMAXN,false);comps.clear();for(inti1;iDP;i)if(!visited[i]){vectorintnodes;dfs(i,nodes);// BFS染色vectorintcolor(nodes.size(),-1);color[0]0;queueintq;q.push(0);while(!q.empty()){intidxq.front();q.pop();intunodes[idx];for(intv:graph[u]){autoitfind(nodes.begin(),nodes.end(),v);if(itnodes.end())continue;intvIdxit-nodes.begin();if(color[vIdx]-1)color[vIdx]1-color[idx],q.push(vIdx);}}// 计算两种方案Comp comp{0,0,0,0,0,0};for(intj0;jnodes.size();j){intnodenodes[j],init(nodeD)?0:1;intfinal0color[j],final11-final0;// 方案0if(init0){if(final00)comp.d0;elsecomp.p0,comp.c0priceD[node];}else{if(final00)comp.d0,comp.c0priceP[node];elsecomp.p0;}// 方案1if(init0){if(final10)comp.d1;elsecomp.p1,comp.c1priceD[node];}else{if(final10)comp.d1,comp.c1priceP[node];elsecomp.p1;}}comps.push_back(comp);}}intsolve(boolforDSP){vectorintdp(B1,0);for(constCompc:comps)for(intbB;b0;--b){if(bc.c0)dp[b]max(dp[b],dp[b-c.c0](forDSP?c.d0:c.p0));if(bc.c1)dp[b]max(dp[b],dp[b-c.c1](forDSP?c.d1:c.p1));}returndp[B];}intmain(){while(cinDPRB){for(inti0;iMAXN;i)graph[i].clear();for(inti1;iD;i)cinpriceD[i];for(intj1;jP;j)cinpriceP[jD];for(inti0;iR;i){intx,y;cinxy;graph[x].push_back(yD);graph[yD].push_back(x);}build();coutsolve(true) solve(false)endl;}return0;}总结本题是一道综合性较强的题目需要结合图论二分图染色和动态规划背包问题进行求解。关键是将原问题分解为连通分量并识别出每个分量只有两种可能的分配方案。通过将问题转化为分组背包可以高效地求解最大人数。算法复杂度合理能够处理题目给定的数据范围。
