UVa 10546 The Eagle‘s Nest

题目翻译与分析

游戏规则理解

《鹰巢》是一款非线性剧情的动作冒险游戏。玩家需要从简单任务开始，通过完成越来越难的任务，最终挑战最困难的任务。游戏的核心机制如下：

1. 任务难度与顺序：每个任务有一个难度值，任务按输入顺序给出，这代表了它们在剧情中的顺序。
2. 任务选择限制：在单次游戏流程中，玩家只能选择难度严格大于所有已完成任务难度的任务。这意味着在单次流程中，完成的任务难度必须是严格递增的。
3. 任务完成状态：一个任务一旦在单次流程中完成，在该次流程中就不能再次选择。
4. 首尾任务特殊性：第一个任务（最简单）和最终任务（最困难）不计入任务总数，并且总是可以被访问。它们相当于固定的起点和终点。
5. 游戏可重复性：玩家可以多次从头开始游戏。每次游戏都从第一个任务开始，到最终任务结束。
6. 目标：设KKK为玩家第一次玩游戏时能够完成的最大任务数（不包括首尾任务）。玩家的目标是，通过多次游戏，在不重复完成任何任务的前提下，最大化完成的任务总数。最终答案就是这个最大总数。

问题转化与建模

理解规则后，我们可以将问题分解为两个关键步骤：

1. 确定单次流程的最大任务数KKK
   在单次游戏中，由于只能选择难度递增的任务，且不能重复，那么能完成的任务序列本质上就是原任务序列的一个严格递增子序列。而第一次玩游戏时能完成的最大任务数KKK，就是整个任务序列的最长严格递增子序列 (LIS\texttt{LIS}LIS)的长度。
   注意：这里我们只关心难度值，任务名称仅用于输入输出，不参与计算。

2. 确定最大可重复流程数
   知道了KKK，我们需要找出最多能进行多少次“游戏流程”，使得每次流程都完成恰好KKK个任务（一条从难度最低层到最高层的路径），并且所有流程中没有任务被重复使用。
   这可以建模为一个图论问题：

   • 将每个任务看作一个节点。
   • 如果任务iii的难度小于任务jjj的难度，并且任务jjj在以iii结尾的LIS\texttt{LIS}LIS中的层级正好比iii大111（即d[j] = d[i] + 1），那么我们就建立一条从iii到jjj的有向边。这样就形成了一个有向无环图 (DAG\texttt{DAG}DAG)。
   • 在这个DAG\texttt{DAG}DAG中，我们需要找到尽可能多的从“层级为111的节点”（对应LIS\texttt{LIS}LIS起点）到“层级为KKK的节点”（对应LIS\texttt{LIS}LIS终点）的路径，并且这些路径之间没有公共节点（即任务不重复）。
   • 这正是DAG\texttt{DAG}DAG上的最大不相交路径覆盖问题。

   对于节点不相交的路径覆盖，可以通过拆点 + 最大流来解决：

   • 将每个任务节点uuu拆成入点uinu_{in}uin​和出点uoutu_{out}uout​，并在它们之间连一条容量为111的边，这保证了每个任务最多被使用一次。
   • 对于原图中的有向边(u,v)(u, v)(u,v)，在流网络中连接uout→vinu_{out} \to v_{in}uout​→vin​，容量为111。
   • 建立超级源点SSS，连接SSS到所有层级为 1 的任务的入点，容量为111。
   • 建立超级汇点TTT，连接所有层级为KKK的任务的出点到TTT，容量为111。
   • 计算从SSS到TTT的最大流，其值就等于最大不相交路径的数量（记为flowflowflow）。

3. 计算最终答案
   每次流程完成KKK个任务，最多能进行flowflowflow次流程，因此能完成的最大任务总数为K×flowK \times flowK×flow。

样例详解

为了更直观地理解题目，我们详细分析题目给出的两个样例：

样例输入111

3 Rob_The_Cop 6 A_Petty_Thief 5 Meet_The_Boss 3

任务难度序列：[6, 5, 3]

分析：

1. 计算KKK：虽然输入顺序是6 → 5 → 3（难度递减），但玩家可以按照难度递增的顺序玩：先玩难度333，然后玩难度555（5>35 > 35>3），最后玩难度666（6>56 > 56>5）。所以最长严格递增子序列是[3, 5, 6]，长度K=3K = 3K=3。
2. 构建图：所有任务都在同一条LIS\texttt{LIS}LIS路径上，因此只能形成一条完整的路径：难度333（层级111）→ 难度555（层级222）→ 难度666（层级333）。
3. 最大流：由于只有一条路径，最大不相交路径数flow=1flow = 1flow=1。
4. 最终答案：K×flow=3×1=3K \times flow = 3 \times 1 = 3K×flow=3×1=3。

样例输入222

3 Meet_The_Boss 3 Rob_The_Cop 6 A_Petty_Thief 5

任务难度序列：[3, 6, 5]

分析：

1. 计算KKK：可能的递增序列有[3, 6]或[3, 5]，长度都是222。注意不能玩[3, 6, 5]，因为玩完难度666后，难度5<65 < 65<6，违反了规则。所以K=2K = 2K=2。
2. 构建图：
   • 任务层级：难度333（层级111），难度666（层级222），难度555（层级 2）
   • 可能的边：难度333→ 难度666，难度333→ 难度555
   • 有两条潜在路径：3 → 6和3 → 5
3. 最大流：由于任务333只能被使用一次（拆点容量为111），所以只能选择其中一条路径，flow=1flow = 1flow=1。
4. 最终答案：K×flow=2×1=2K \times flow = 2 \times 1 = 2K×flow=2×1=2。

样例输出

Case #1: 3 Case #2: 2

关键启示：样例111和样例222包含了相同的三个任务，只是输入顺序不同，导致答案不同。这凸显了任务难度值本身比输入顺序更重要的规则特性。玩家可以跳过中间的任务，只要保证每次新玩的任务都比之前所有玩过的任务都难即可。

算法流程总结

1. 输入任务，提取难度值数组vvv。
2. 动态规划计算LIS\texttt{LIS}LIS长度KKK，同时记录每个任务在LIS\texttt{LIS}LIS中的层级d[i]d[i]d[i]（即以该任务结尾的LIS\texttt{LIS}LIS长度）。
3. 根据层级关系构建DAG\texttt{DAG}DAG，并使用拆点法建立流网络。
4. 使用最大流算法（如Dinic\texttt{Dinic}Dinic、Edmonds-Karp\texttt{Edmonds-Karp}Edmonds-Karp）计算最大流flowflowflow。
5. 输出答案K×flowK \times flowK×flow。

代码实现

// The Eagle's Nest// UVa ID: 10546// Verdict: Accepted// Submission Date: 2025-12-17// UVa Run Time: 0.000s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){intcaseNumber=1;// 测试用例编号intN;// 任务数量while(cin>>N&&N!=0){// 读取任务，名称和难度vector<pair<string,int>>missions(N);for(inti=0;i<N;i++)cin>>missions[i].first>>missions[i].second;// 提取难度值vector<int>v(N);for(inti=0;i<N;i++)v[i]=missions[i].second;// 第一步：计算最长严格递增子序列(LIS)的长度K，并记录每个任务的层级d[i]vector<int>d(N,1);// d[i]表示以任务i结尾的LIS长度intmaxLen=1;// 即K值for(inti=0;i<N;i++){for(intj=0;j<i;j++){if(v[j]<v[i]&&d[j]+1>d[i]){d[i]=d[j]+1;}}maxLen=max(maxLen,d[i]);}// 第二步：构建网络流图求解最大不相交路径数// 节点编号：0-源点，1~N为任务入点，N+1~2N为任务出点，2N+1为汇点intsource=0,sink=2*N+1;vector<vector<int>>cap(2*N+2,vector<int>(2*N+2,0));// 任务拆点：每个任务入点到出点容量为1，保证每个任务只被用一次for(inti=0;i<N;i++){cap[i+1][i+1+N]=1;}// 源点连接所有第一层任务（d[i]==1）for(inti=0;i<N;i++){if(d[i]==1){cap[source][i+1]=1;}}// 所有最后一层任务（d[i]==K）连接汇点for(inti=0;i<N;i++){if(d[i]==maxLen){cap[i+1+N][sink]=1;}}// 根据层级关系连接任务：如果v[i] < v[j] 且 d[j] == d[i] + 1，则连边for(inti=0;i<N;i++){for(intj=i+1;j<N;j++){if(v[i]<v[j]&&d[j]==d[i]+1){// 从i的出点连接到j的入点cap[i+1+N][j+1]=1;}}}// Dinic 最大流算法autobfs=[&](vector<int>&level)->bool{fill(level.begin(),level.end(),-1);queue<int>q;q.push(source);level[source]=0;while(!q.empty()){intu=q.front();q.pop();for(intv=0;v<=sink;v++){if(level[v]==-1&&cap[u][v]>0){level[v]=level[u]+1;q.push(v);}}}returnlevel[sink]!=-1;};function<int(int,int,vector<int>&)>dfs=[&](intu,intflow,vector<int>&level)->int{if(u==sink)returnflow;for(intv=0;v<=sink;v++){if(level[v]==level[u]+1&&cap[u][v]>0){intpushed=dfs(v,min(flow,cap[u][v]),level);if(pushed>0){cap[u][v]-=pushed;cap[v][u]+=pushed;returnpushed;}}}return0;};intmaxFlow=0;vector<int>level(sink+1);while(bfs(level)){while(intpushed=dfs(source,INT_MAX,level)){maxFlow+=pushed;}}// 第三步：计算最终答案 = K * 最大不相交路径数intresult=maxLen*maxFlow;cout<<"Case #"<<caseNumber++<<": "<<result<<endl;}return0;}