P1137 旅行计划【洛谷算法习题】

P1137 旅行计划网页链接P1137 旅行计划题目描述小明要去一个国家旅游。这个国家有N NN个城市编号为1 11至N NN并且有M MM条道路连接着小明准备从其中一个城市出发并只往东走到城市i ii停止。所以他就需要选择最先到达的城市并制定一条路线以城市i ii为终点使得线路上除了第一个城市每个城市都在路线前一个城市东面并且满足这个前提下还希望游览的城市尽量多。现在你只知道每一条道路所连接的两个城市的相对位置关系但并不知道所有城市具体的位置。现在对于所有的i ii都需要你为小明制定一条路线并求出以城市i ii为终点最多能够游览多少个城市。输入格式第一行为两个正整数N , M N, MN,M。接下来M MM行每行两个正整数x , y x, yx,y表示了有一条连接城市x xx与城市y yy的道路保证了城市x xx在城市y yy西面。输出格式N NN行第i ii行包含一个正整数表示以第i ii个城市为终点最多能游览多少个城市。输入输出样例 #1输入 #15 6 1 2 1 3 2 3 2 4 3 4 2 5输出 #11 2 3 4 3说明/提示均选择从城市1 11出发可以得到以上答案。对于20 % 20\%20%的数据1 ≤ N ≤ 100 1\le N ≤ 1001≤N≤100对于60 % 60\%60%的数据1 ≤ N ≤ 1000 1\le N ≤ 10001≤N≤1000对于100 % 100\%100%的数据1 ≤ N ≤ 100000 1\le N ≤ 1000001≤N≤1000001 ≤ M ≤ 200000 1\le M ≤ 2000001≤M≤200000。解题思路本题核心是拓扑排序动态规划求解有向无环图D A G DAGDAG的最长路径问题。题目中道路为有向边x → y x \to yx→yx xx在西y yy在东保证图无环。定义d p [ i ] dp[i]dp[i]表示以城市i ii为终点最多能游览的城市数初始值全部为1 11。首先通过拓扑排序得到节点的合法处理顺序确保遍历节点时其所有前驱节点已完成计算。按照拓扑序遍历每个节点对其邻接节点进行状态转移d p [ v ] max ⁡ ( d p [ v ] , d p [ u ] 1 ) dp[v] \max(dp[v], dp[u]1)dp[v]max(dp[v],dp[u]1)。最终输出d p dpdp数组即为答案整体时间复杂度O ( N M ) O(NM)O(NM)完美适配大数据范围。总结核心逻辑将问题转化为D A G DAGDAG最长路问题利用拓扑序保证动态规划的正确转移。关键操作建图统计入度拓扑排序确定计算顺序线性递推更新最长路径长度。效率保障线性时间复杂度无冗余计算高效处理10 5 10^5105节点、2 × 10 5 2 \times 10^52×105边的规模。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N1e510;constll p1e97;constll INF1e18;constll M2e310;ll n,m,sum,tot;ll h[N],ru[N],ts[N],dp[N];structedge{ll to;ll next;}ed[N2];voidadd(ll x,ll y){ed[sum].nexth[x];ed[sum].toy;h[x]sum;}voidtopsort(){queuellq;for(ll i1;in;i)if(ru[i]0){q.push(i);ts[tot]i;}while(!q.empty()){ll uq.front();q.pop();for(ll ih[u];i;ied[i].next){ll ved[i].to;ru[v]--;if(ru[v]0){q.push(v);ts[tot]v;}}}}intmain(){cinnm;for(ll i1;im;i){ll u,v;cinuv;add(u,v);ru[v];}topsort();for(ll i1;in;i)dp[i]1;for(ll i1;in;i){ll uts[i];for(ll jh[u];j;jed[j].next){ll ved[j].to;dp[v]max(dp[v],dp[u]1);}}for(ll i1;in;i)coutdp[i]endl;return0;}