题目描述
在一个有向图网络中，节点代表机器或路由器，有向边表示数据可以沿该方向传输。两个节点之间要通信，需要存在从第一个节点到第二个节点的有向路径，以及从第二个节点到第一个节点的有向路径。ICPC\texttt{ICPC}ICPC公司的系统要求在通信双方以及两条路径上的所有中间节点都安装软件。软件安装费用按安装节点数计算。给定网络和需要通信的两个节点（节点111和节点222），要求找到最便宜的安装方案，即选择最少的节点安装软件，使得节点111和节点222之间可以双向通信。
输入格式
输入包含多组测试数据。每组数据第一行给出两个整数NNN和MMM（2≤N≤1002 \le N \le 1002≤N≤100），分别表示节点数量和边数量。节点编号为111到NNN，其中节点111和节点222是需要通信的两个节点。接下来MMM行每行两个整数XXX和YYY，表示存在一条从XXX到YYY的有向边。输入以一行0 0结束。
输出格式
对每组测试数据，先输出Network X，其中XXX为测试数据编号。然后输出Minimum number of nodes = K，其中KKK为需要安装软件的最少节点数（包括节点111和节点222）。若节点111和节点222无法通信，输出Impossible。每组数据输出后跟一个空行。
样例输入
8 12 1 3 3 4 4 2 2 5 5 6 6 1 1 7 7 1 8 7 7 8 8 2 2 8 2 1 1 2 0 0样例输出
Network 1 Minimum number of nodes = 4 Network 2 Impossible题目分析
本题要求选择最少的节点安装软件，使得节点111可以到达节点222，且节点222可以到达节点111，且路径上所有中间节点都已安装软件。由于软件安装费用与节点数成正比，目标是最小化安装节点的数量。注意，节点111和节点222必须安装软件（题目要求计数包括它们），其他节点可以选择安装或不安装。
该问题可以建模为在状态空间上的最短路径问题。状态由两个节点(x,y)(x, y)(x,y)组成，表示当前已经为从节点111到节点222的路径和从节点222到节点111的路径分别选择了部分节点。更具体地，设dp[x][y]dp[x][y]dp[x][y]表示从初始状态(1,1)(1, 1)(1,1)出发，已经确定了一条从111到xxx的路径和一条从111到yyy的路径（方向相反，但可以对称处理），使得这两条路径上的节点都已安装软件，所需的最少安装节点数。初始状态为(1,1)(1, 1)(1,1)，dp[1][1]=1dp[1][1] = 1dp[1][1]=1（只安装了节点111）。目标状态为(2,2)(2, 2)(2,2)，表示两条路径都到达了节点222，此时dp[2][2]dp[2][2]dp[2][2]即为最少安装节点数。
状态转移时，可以从当前状态(x,y)(x, y)(x,y)出发，沿一条有向边从xxx扩展到iii（即dist[x][i]=1dist[x][i] = 1dist[x][i]=1），或者从yyy扩展到iii（即dist[i][y]=1dist[i][y] = 1dist[i][y]=1）。若新节点iii尚未在两条路径中出现（即i≠xi \ne xi=x且i≠yi \ne yi=y），则需要额外安装一个节点，代价为111；否则代价为000。此外，当x≠yx \ne yx=y时，还可以考虑将两条路径“合并”，即利用从xxx到yyy的最短路径，一次性将路径从xxx推进到yyy（或从yyy推进到xxx），此时需要安装的节点数为dist[x][y]−1dist[x][y] - 1dist[x][y]−1（因为路径上的中间节点需要安装，而端点已安装）。这一合并操作可以加速收敛，避免逐节点扩展。
由于状态数最多为N2=10000N^2 = 10000N2=10000，使用队列进行SPFA\texttt{SPFA}SPFA式的松弛操作可以在合理时间内求解。代码中dp[x][y]表示两条路径分别到达xxx和yyy时的最小安装节点数，visited[x][y]用于标记状态是否在队列中。初始时dp[1][1] = 1，将(1,1)(1, 1)(1,1)入队。每次取出状态(x,y)(x, y)(x,y)，尝试沿一条边从xxx扩展到iii，或从yyy扩展到iii，以及当x≠yx \ne yx=y时利用dist[x][y]dist[x][y]dist[x][y]进行合并。若更新了dp值且新状态未在队列中，则入队。
最终，若dp[2][2]仍为无穷大，说明无法通信，输出Impossible；否则输出dp[2][2]。
时间复杂度：状态数为O(N2)O(N^2)O(N2)，每个状态最多尝试O(N)O(N)O(N)次转移，总时间复杂度为O(N3)O(N^3)O(N3)。在N≤100N \le 100N≤100的约束下，计算量约为10610^6106，完全可行。空间复杂度为O(N2)O(N^2)O(N2)，用于存储距离矩阵和dp\texttt{dp}dp数组。
解题思路
步骤1\texttt{1}1. 读取节点数NNN和边数MMM，若N=0N = 0N=0则结束。
步骤2\texttt{2}2. 初始化距离矩阵dist，所有元素设为无穷大。读取MMM条有向边，将dist[x][y]设为111。
步骤3\texttt{3}3. 使用Floyd\texttt{Floyd}Floyd算法计算所有节点对之间的最短路径长度，得到dist[i][j]表示从iii到jjj的最少边数。
步骤4\texttt{4}4. 初始化dp\texttt{dp}dp数组，所有元素设为无穷大。dp[1][1] = 1。初始化队列，将状态(1,1)(1, 1)(1,1)入队，并标记visited[1][1] = 1。
步骤5\texttt{5}5. 当队列非空时，取出队首状态(x,y)(x, y)(x,y)，标记visited[x][y] = 0。对于每个节点iii（从111到NNN）：
- 若
dist[x][i] == 1，则尝试从xxx扩展到iii。计算代价cost = (x != i && y != i)。若dp[i][y] > dp[x][y] + cost，则更新dp[i][y]，若新状态未入队则入队。 - 若
dist[i][y] == 1，则尝试从yyy扩展到iii。计算代价cost = (x != i && y != i)。若dp[x][i] > dp[x][y] + cost，则更新dp[x][i]，若新状态未入队则入队。 - 若x≠yx \ne yx=y，尝试合并路径：若
dp[y][x] > dp[x][y] + dist[x][y] - 1，则更新dp[y][x]，若新状态未入队则入队。
步骤6\texttt{6}6. 输出Network X，其中XXX为测试数据编号。若dp[2][2]为无穷大，输出Impossible；否则输出Minimum number of nodes = dp[2][2]。输出后跟一个空行。
代码实现
// Routing// UVa ID: 1057// Verdict: Accepted// Submission Date: 2018-07-12// UVa Run Time: 0.030s//// 版权所有（C）2018，邱秋。metaphysis # yeah dot net//// http://apps.topcoder.com/forums/?module=Thread&threadID=662332&start=0#include<bits/stdc++.h>usingnamespacestd;constintINF=0x3f3f3f3f;intdist[105][105],dp[105][105],visited[105][105];intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intn,m,x,y;intcases=0;while(cin>>n>>m,n){memset(visited,0,sizeof(visited));for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)dist[i][j]=INF;for(inti=0;i<m;i++){cin>>x>>y;dist[x][y]=1;}for(intk=1;k<=n;k++)for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)dp[i][j]=INF;queue<pair<int,int>>q;q.push(make_pair(1,1));dp[1][1]=1;pair<int,int>p;while(!q.empty()){p=q.front(),q.pop();x=p.first,y=p.second;visited[x][y]=0;for(inti=1;i<=n;i++){intcost=(x!=i&&y!=i);if(dist[x][i]==1&&dp[i][y]>dp[x][y]+cost){dp[i][y]=dp[x][y]+cost;if(!visited[i][y]){visited[i][y]=1;q.push(make_pair(i,y));}}if(dist[i][y]==1&&dp[x][i]>dp[x][y]+cost){dp[x][i]=dp[x][y]+cost;if(!visited[x][i]){visited[x][i]=1;q.push(make_pair(x,i));}}}if(x!=y){if(dp[y][x]>dp[x][y]+dist[x][y]-1){dp[y][x]=dp[x][y]+dist[x][y]-1;if(!visited[y][x]){visited[y][x]=1;q.push(make_pair(y,x));}}}}cout<<"Network "<<++cases<<"\n";if(dp[2][2]==INF)cout<<"Impossible\n";elsecout<<"Minimum number of nodes = "<<dp[2][2]<<'\n';cout<<'\n';}return0;}总结
本题的核心是选择最少的节点安装软件，使得节点111和节点222之间可以双向通信。通过将问题建模为状态空间上的最短路径，其中状态(x,y)(x, y)(x,y)表示两条路径分别到达xxx和yyy，使用SPFA\texttt{SPFA}SPFA算法进行松弛操作。状态转移包括沿单条边扩展以及利用最短路径进行合并。最终dp[2][2]即为最少安装节点数。该解法充分利用了N≤100N \le 100N≤100的规模，状态数有限，能够在规定时间内求解。需要注意初始状态dp[1][1] = 1表示只安装了节点111，而节点222的安装会在路径到达时计入代价。
