题意:https://www.luogu.com.cn/problem/P1137
小明要去一个国家旅游。这个国家有#NN个城市，编号为1至N，并且有MM条道路连接着，小明准备从其中一个城市出发，并只往东走到城市i停止。
所以他就需要选择最先到达的城市，并制定一条路线以城市i为终点，使得线路上除了第一个城市，每个城市都在路线前一个城市东面，并且满足这个前提下还希望游览的城市尽量多。
现在，你只知道每一条道路所连接的两个城市的相对位置关系，但并不知道所有城市具体的位置。现在对于所有的i，都需要你为小明制定一条路线，并求出以城市i为终点最多能够游览多少个城市。
刚开始写的时候，傻乎乎的以为是最长路，可又不能对每个节点跑一次最长路。
仔细想想，建立反向边也不好使，于是我画了个图。
样例画出来是这样的。很明显以1为终点只能浏览到1
为什么呢?因为1没有入度，没有指向它的边，这是不是在暗示我们拓扑呢？
其实这是一个DP+拓扑。
#include <bits/stdc++.h> using namespace std; const int maxn=200009; int dp[100009]; struct p{ int to,nxt,w; }d[maxn];int cnt=1,head[maxn],dis[100009]; void add(int u,int v,int w){ d[cnt].to=v,d[cnt].w=w, d[cnt].nxt=head[u],head[u]=cnt++; } int indug[100009],n,m; void tuopu() { queue<int>q; for(int i=1;i<=n;i++) if(indug[i]==0) q.push(i); while(!q.empty()) { int ans=q.front();q.pop(); for(int i=head[ans];i;i=d[i].nxt) { int w=d[i].to; dp[w]=max(dp[w],dp[ans]+1); if(--indug[w]==0) q.push(w); } } } int main() { cin>>n>>m; for(int i=1;i<=m;i++) { int l,r; cin>>l>>r; add(l,r,1); indug[r]++; } tuopu(); for(int i=1;i<=n;i++) cout<<dp[i]+1<<endl; }
原文链接: https://www.cnblogs.com/iss-ue/p/12509853.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/374099
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
