UVa 12264 Risk

题目分析在一个棋盘游戏Risk\texttt{Risk}Risk中玩家控制若干区域每个区域有若干军队。玩家可以在自己控制的相邻区域之间移动军队移动过程中每个区域必须始终至少保留一个军队。目标是经过一个回合的移动后使得所有与对手区域相邻的我方区域称为边界区域中军队数量的最小值尽可能大。换句话说我们需要最大化一个值targettargettarget使得存在一种移动方案让每个边界区域的军队数都至少达到targettargettarget同时满足移动过程中的约束。解题思路这是一个典型的最大值最小化问题通常可以用二分答案 可行性检查的方法解决。二分答案框架下界lowlowlow初始时所有边界区域军队数量的最小值。上界highhighhigh我方所有军队的总数因为军队不可能超过总数。在[low,high][low, high][low,high]范围内二分查找对于每个midmidmid判断是否能让所有边界区域的军队数都≥mid\ge mid≥mid。可行性检查的核心难点移动军队时有两个关键约束每个区域在任何时刻至少保留一个军队。军队只能在自己控制的相邻区域间移动。直接模拟移动过程非常复杂我们需要一个数学模型来描述军队的重新分配。网络流建模本题的标准解法是使用最大流来检查可行性。建模的关键在于如何正确表示军队的流动和最终分布。拆点技巧每个我方区域iii拆成两个节点入点iii表示区域本身出点ini nin表示从该区域流出的军队为什么需要拆点拆点可以精确控制每个区域的军队数量区域iii最终的军队数 从源点流入iii出点的军队 区域原有的军队 - 从iii出点流出的军队。通过入点和出点之间的边容量我们可以限制每个区域最终保留的军队数。边的含义出点→\rightarrow→入点容量为a[i]a[i]a[i]区域原有的军队数。这条边表示区域iii原有的军队必须经过它才能流动到其他地方且不能超过原有数量。源点sss→\rightarrow→出点容量根据区域类型不同如果是边界区域容量为a[i]a[i]a[i]所有军队都可以调出如果是内部区域容量为a[i]−1a[i] - 1a[i]−1必须保留一个军队源点代表“可以重新分配的军队池”这些军队可以流向任何需要的地方。入点iii→\rightarrow→出点jnjnjn如果区域iii和jjj相邻且都是我方的则添加容量为∞\infty∞的边。这表示军队可以从区域iii移动到区域jjj通过iii的入点流入jjj的出点。出点→\rightarrow→汇点ttt仅对边界区域添加容量为midmidmid。这条边表示该边界区域最终需要保留midmidmid个军队。如果最大流能将这些边全部填满就说明所有边界区域都能达到targettargettarget。可行性判断设边界区域的数量为mmm则所有边界区域需要的军队总数为m×midm \times midm×mid。计算从源点到汇点的最大流flowflowflow如果flow≥m×midflow \ge m \times midflow≥m×mid说明midmidmid可行。为什么这个建模是正确的军队守恒每个区域原有的军队通过“出点→\rightarrow→入点”的边进入系统最终通过“出点→\rightarrow→汇点”的边离开系统对边界区域或留在系统中对内部区域。移动约束军队只能通过“入点→\rightarrow→出点”的边在相邻区域间移动。最低保留约束内部区域的源点连接容量为a[i]−1a[i]-1a[i]−1确保了至少保留一个军队边界区域的汇点连接容量为midmidmid确保了最终数量。代码实现// Risk// UVa ID: 12264// Verdict: Accepted// Submission Date: 2026-02-23// UVa Run Time: 0.010s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintINF10000;constintMAXN205;classDinic{private:structEdge{intto,cap,flow,rev;};vectorEdgeadj[MAXN];intlevel[MAXN],cur[MAXN];public:voidclear(){for(inti0;iMAXN;i)adj[i].clear();}voidaddEdge(intu,intv,intcap){adj[u].push_back({v,cap,0,(int)adj[v].size()});adj[v].push_back({u,0,0,(int)adj[u].size()-1});}boolbfs(ints,intt){memset(level,-1,sizeof(level));queueintq;level[s]0;q.push(s);while(!q.empty()){intuq.front();q.pop();for(autoe:adj[u]){if(level[e.to]0e.cape.flow){level[e.to]level[u]1;q.push(e.to);}}}returnlevel[t]0;}intdfs(intu,intt,intf){if(ut)returnf;for(inticur[u];i(int)adj[u].size();i){Edgeeadj[u][i];if(level[e.to]level[u]1e.cape.flow){intddfs(e.to,t,min(f,e.cap-e.flow));if(d0){e.flowd;adj[e.to][e.rev].flow-d;returnd;}}}return0;}intmaxFlow(ints,intt){intflow0;while(bfs(s,t)){memset(cur,0,sizeof(cur));intf;while((fdfs(s,t,INF))0)flowf;}returnflow;}};intmain(){ios::sync_with_stdio(false);cin.tie(0);intT;cinT;while(T--){intn;cinn;vectorintarmy(n1);inttotalArmy0;for(inti1;in;i){cinarmy[i];totalArmyarmy[i];}vectorboolisBorder(n1,false);vectorvectorbooladj(n1,vectorbool(n1,false));for(inti1;in;i){string line;cinline;for(intj1;jn;j){if(line[j-1]Y){adj[i][j]true;if(army[i]0army[j]0)isBorder[i]true;}}}intborderCount0;for(inti1;in;i)if(isBorder[i])borderCount;intleft1,righttotalArmy,ans0;while(leftright){intmid(leftright)/2;Dinic dinic;ints0,t2*n1;for(inti1;in;i){if(army[i]0)continue;dinic.addEdge(in,i,army[i]);if(isBorder[i]){dinic.addEdge(s,in,army[i]);dinic.addEdge(in,t,mid);}else{dinic.addEdge(s,in,army[i]-1);}}for(inti1;in;i){if(army[i]0)continue;for(intj1;jn;j){if(i!jadj[i][j]army[j]0)dinic.addEdge(i,jn,INF);}}intflowdinic.maxFlow(s,t);if(flowborderCount*mid){ansmid;leftmid1;}else{rightmid-1;}}coutansendl;}return0;}复杂度分析每次maxFlow\texttt{maxFlow}maxFlow调用使用Dinic\texttt{Dinic}Dinic算法复杂度O(EV)O(E \sqrt{V})O(EV​)其中V2n2V 2n 2V2n2EO(n2)E O(n^2)EO(n2)。二分查找次数为O(log⁡∑ai)O(\log \sum a_i)O(log∑ai​)总复杂度O(n2nlog⁡∑ai)O(n^2 \sqrt{n} \log \sum a_i)O(n2n​log∑ai​)在n≤100n \le 100n≤100时完全可行。