UVa 1306 The K-League-洪萨配资

题目描述

K \texttt{K}K联赛（原韩国职业足球联赛）正在进行中，每支球队都有支持者为其助威。在赛季进行到某个阶段后，支持者们想知道他们支持的球队S SS是否还有可能赢得冠军（允许并列冠军）。具体来说，问题是：给定当前每支球队的胜场数w i w_iwi和负场数d i d_idi，以及每对球队之间剩余的比赛场数a i , j a_{i,j}ai,j，能否为剩余的所有比赛分配胜者，使得最终没有球队的总胜场数超过球队S SS的总胜场数？

输入格式：

第一行：测试用例数T TT
每个测试用例包含三行：
1. 球队数n ( 1 ≤ n ≤ 25 ) n(1 \leq n \leq 25)n(1≤n≤25)
2. 2 n 2n2n个非负整数w 1 , d 1 , w 2 , d 2 , … , w n , d n w_1,d_1,w_2,d_2,\ldots,w_n,d_nw1,d1,w2,d2,…,wn,dn，每个≤ 100 \leq 100≤100
3. n 2 n^2n2个非负整数a 1 , 1 , a 1 , 2 , … , a n , n a_{1,1},a_{1,2},\ldots,a_{n,n}a1,1,a1,2,…,an,n，每个≤ 10 \leq 10≤10，表示剩余比赛场数，保证a i , j = a j , i a_{i,j}=a_{j,i}ai,j=aj,i且a i , i = 0 a_{i,i}=0ai,i=0

输出格式：
对于每个测试用例，输出一行，按编号递增顺序输出所有可能夺冠的球队编号。

题目分析

这个问题本质上是一个可行性判断问题：对于每支候选球队x xx，判断是否存在一种剩余比赛的胜负分配方案，使得所有球队的最终胜场数都不超过球队x xx的最大可能胜场数。

关键观察

胜场数上限：对于球队x xx，假设它剩余的所有比赛全胜，那么它的最大可能胜场数为：
m a x W i n = w x + ∑ j = 1 n a x , j maxWin = w_x + \sum_{j=1}^{n} a_{x,j}maxWin=wx+j=1∑nax,j
约束条件：对于其他任何球队i ii，其最终胜场数不能超过m a x W i n maxWinmaxWin，即：
w i + ( 球队 i 在剩余比赛中获得的胜场数 ) ≤ m a x W i n w_i + (\text{球队$i$在剩余比赛中获得的胜场数}) \leq maxWinwi+(球队i在剩余比赛中获得的胜场数)≤maxWin
等价于：
球队 i 在剩余比赛中最多还能赢 m a x W i n − w i 场 \text{球队$i$在剩余比赛中最多还能赢} \quad maxWin - w_i \quad \text{场}球队i在剩余比赛中最多还能赢maxWin−wi场
比赛分配：每场剩余比赛必须在两个参赛队伍之间分配一个胜场。

转化为网络流问题

这是一个典型的多源多汇分配问题，可以转化为最大流问题来判断可行性。

建图方法

对于每个待检查的球队x xx，我们构建这样一个流网络：

节点类型：
- 源点s o u r c e sourcesource
- 每场剩余比赛一个节点（如果a i , j > 0 a_{i,j} > 0ai,j>0且i < j i < ji<j）
- 每支球队一个节点
- 汇点s i n k sinksink
边与容量：
- 从源点到每场比赛节点：容量为该比赛剩余场数a i , j a_{i,j}ai,j
- 从比赛节点到对应的两支球队节点：容量为无穷大（表示这场比赛的胜场可以分配给任意一支参赛队伍）
- 从球队节点到汇点：容量为m a x W i n − w i maxWin - w_imaxWin−wi（表示该球队最多还能赢多少场）
可行性判断：
计算从源点到汇点的最大流。如果最大流等于所有剩余比赛的总场数，说明存在一种分配方案，使得所有球队的胜场数都不超过m a x W i n maxWinmaxWin，即球队x xx可能夺冠。

为什么这样是正确的？

从源点到比赛节点的流量表示这场比赛被"使用"的次数（即需要分配胜负的场次）。
从比赛节点到球队节点的边保证了每场比赛的胜者必须是参赛的两支球队之一。
从球队节点到汇点的容量限制了每支球队最多能增加的胜场数。
如果最大流等于总剩余比赛数，意味着所有比赛都被成功分配，且没有球队超过胜场限制。

算法复杂度

对于每支待检查的球队：

节点数：最多C 25 2 + 25 + 2 ≈ 327 C_{25}^2 + 25 + 2 \approx 327C252+25+2≈327个
边数：约为比赛节点数的3 33倍
使用 Dinic 算法求最大流：O ( E V ) O(E\sqrt{V})O(EV)或O ( V 2 E ) O(V^2E)O(V2E)在实际中表现良好

总复杂度：O ( n ⋅ maxflow ( V , E ) ) O(n \cdot \text{maxflow}(V,E))O(n⋅maxflow(V,E))，在n ≤ 25 n \leq 25n≤25的情况下完全可行。

解题思路步骤

读取输入：处理T TT个测试用例。
检查每支球队：对于每支球队i ii，调用判断函数canWin(i)。
判断函数实现：
- 计算目标球队的最大可能胜场m a x W i n maxWinmaxWin。
- 快速检查：如果有任何球队当前胜场w j > m a x W i n w_j > maxWinwj>maxWin，直接返回false。
- 构建流网络：
  - 统计所有剩余比赛（a u , v > 0 a_{u,v} > 0au,v>0且u < v u < vu<v）。
  - 创建源点、比赛节点、球队节点、汇点。
  - 添加相应边。
- 计算最大流，判断是否等于总剩余比赛数。
输出结果：按编号递增顺序输出所有可能夺冠的球队。

代码实现

// The K-League// UVa ID: 1306// Verdict: Accepted// Submission Date: 2025-12-15// UVa Run Time: 0.120s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structEdge{intto,rev;// 目标节点, 反向边在邻接表中的索引intflow,cap;// 当前流量, 容量Edge(intt,intr,intf,intc):to(t),rev(r),flow(f),cap(c){}};constintINF=1e9;// 无穷大常量// Dinic 最大流算法实现structDinic{vector<vector<Edge>>graph;// 邻接表存图vector<int>level,iter;// 分层图中的层级, 当前弧优化intn;// 节点数Dinic(intnodes){n=nodes;graph.resize(nodes);level.resize(nodes);iter.resize(nodes);}// 添加有向边 from->to, 容量为capvoidaddEdge(intfrom,intto,intcap){Edgea(to,graph[to].size(),0,cap);Edgeb(from,graph[from].size(),0,0);// 反向边初始容量为0graph[from].push_back(a);graph[to].push_back(b);}// BFS构建分层图boolbfs(ints,intt){fill(level.begin(),level.end(),-1);queue<int>q;level[s]=0;q.push(s);while(!q.empty()){intcur=q.front();q.pop();for(Edge&e:graph[cur]){if(level[e.to]==-1&&e.flow<e.cap){level[e.to]=level[cur]+1;q.push(e.to);}}}returnlevel[t]!=-1;// 如果汇点可达, 返回true}// DFS寻找增广路intdfs(intcur,intt,intf){if(cur==t)returnf;for(int&i=iter[cur];i<(int)graph[cur].size();++i){Edge&e=graph[cur][i];if(e.flow<e.cap&&level[e.to]==level[cur]+1){intpushed=dfs(e.to,t,min(f,e.cap-e.flow));if(pushed>0){e.flow+=pushed;graph[e.to][e.rev].flow-=pushed;// 更新反向边returnpushed;}}}return0;}// 计算从s到t的最大流intmaxFlow(ints,intt){intflow=0;while(bfs(s,t)){fill(iter.begin(),iter.end(),0);while(intpushed=dfs(s,t,INF)){flow+=pushed;}}returnflow;}};// 判断指定队伍targetTeam是否可能夺冠boolcanWin(inttargetTeam,vector<int>&wins,vector<vector<int>>&remain,intn){// 计算目标队伍的最大可能胜场数（假设剩余比赛全胜）intmaxWin=wins[targetTeam];for(inti=0;i<n;++i){maxWin+=remain[targetTeam][i];}// 快速检查：如果有队伍当前胜场已超过maxWin, 直接返回falsefor(inti=0;i<n;++i){if(wins[i]>maxWin)returnfalse;}// 统计剩余比赛：只考虑i<j的情况, 避免重复intmatchCount=0;vector<pair<int,int>>matches;// 存储比赛双方编号for(inti=0;i<n;++i){for(intj=i+1;j<n;++j){if(remain[i][j]>0){matchCount++;matches.push_back({i,j});}}}// 节点编号分配：// 0 = 源点source// 1 ~ matchCount = 比赛节点// matchCount+1 ~ matchCount+n = 球队节点// matchCount+n+1 = 汇点sinkinttotalNodes=2+matchCount+n;intsource=0;intsink=totalNodes-1;intmatchStart=1;intteamStart=matchStart+matchCount;// 创建Dinic实例Dinicdinic(totalNodes);// 计算总剩余比赛场数inttotalRemainGames=0;// 添加边：源点 -> 比赛节点for(inti=0;i<matchCount;++i){intu=matches[i].first;intv=matches[i].second;intgames=remain[u][v];dinic.addEdge(source,matchStart+i,games);totalRemainGames+=games;// 比赛节点 -> 两支参赛队伍节点（容量为INF，表示可以任意分配）dinic.addEdge(matchStart+i,teamStart+u,INF);dinic.addEdge(matchStart+i,teamStart+v,INF);}// 添加边：球队节点 -> 汇点for(inti=0;i<n;++i){intcap=maxWin-wins[i];// 该队伍最多还能赢几场if(cap<0)returnfalse;// 不应该发生（前面已检查过）dinic.addEdge(teamStart+i,sink,cap);}// 计算最大流intflow=dinic.maxFlow(source,sink);// 如果最大流等于总剩余比赛数，说明所有比赛都能被分配returnflow==totalRemainGames;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);// 加速输入输出inttestCases;cin>>testCases;while(testCases--){intn;cin>>n;vector<int>wins(n);vector<int>defeats(n);// 负场数，实际上在解题中用不到// 读取胜场和负场for(inti=0;i<n;++i){cin>>wins[i]>>defeats[i];}// 读取剩余比赛矩阵vector<vector<int>>remain(n,vector<int>(n));for(inti=0;i<n;++i){for(intj=0;j<n;++j){cin>>remain[i][j];}}// 检查每支队伍是否可能夺冠vector<int>result;for(inti=0;i<n;++i){if(canWin(i,wins,remain,n)){result.push_back(i+1);// 队伍编号从1开始}}// 输出结果（按编号递增顺序）for(size_t i=0;i<result.size();++i){if(i>0)cout<<" ";cout<<result[i];}cout<<endl;}return0;}

算法正确性证明

该算法的正确性基于以下事实：

完备性：如果存在一种分配方案使得球队x xx可能夺冠，那么对应的流网络存在大小为总剩余比赛数的流。
- 构造方法：按照分配方案，每场比赛的胜场流向对应的球队节点。
可靠性：如果流网络存在大小为总剩余比赛数的流，那么可以构造出一种分配方案。
- 从流网络中提取：对于每条从比赛节点到球队节点的边，其流量表示该球队从这场比赛中获得的胜场数。
容量限制：球队节点到汇点的容量m a x W i n − w i maxWin - w_imaxWin−wi保证了没有球队的胜场会超过m a x W i n maxWinmaxWin。

时间复杂度分析

对于每个测试用例：

有n nn支队伍需要检查，每检查一支队伍需要：
- 构建流网络：O ( n 2 ) O(n^2)O(n2)
- 运行 Dinic 算法：O ( V 2 E ) O(V^2E)O(V2E)或O ( E V ) O(E\sqrt{V})O(EV)，其中V ≈ n ( n − 1 ) 2 + n + 2 V \approx \frac{n(n-1)}{2} + n + 2V≈2n(n−1)+n+2，E ≈ 3 × n ( n − 1 ) 2 E \approx 3 \times \frac{n(n-1)}{2}E≈3×2n(n−1)