为什么这个算法不能找到有向无环图中最长的路径?

dp[i]存储了以i为终点的最长路径,对于从x到y的每一条边,我将dp[y]更新为dp[y]和dp[x+1]之间的最大值。

它在输入输出的例子上可以工作,但在判断的时候,一些测试案例失败了。Havent been able to think of a test case in which it fails.Any help would be appreciated.

N是顶点数 M是边数 x y表示从x到y的一条边 输出应该是图中最长路径的长度。

  • 示例输入 N M x1 y1 x2 y2 x3 y3 … …。輸入 1 4 5 1 2 1 3 3 2 2 4 3 4 輸出 1 3 輸入 2 5 8 5 3 2 3 2 4 5 2 5 1 1 4 4 3 1 3 輸出 2 3
#include <bits/stdc++.h>
using namespace std;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,m;
    cin>>n>>m;

    vector<int> dp(n+1,0);
    //dp[i] denotes max length of path ending at node i
    int x,y;
    for(int i=0;i<m;i++)
    {
        cin>>x>>y;
        dp[y]=max(dp[x]+1,dp[y]);
    }
    int ans=0;
    // for(int i=0;i<n+1;i++)
    //  cout<<i<< " : "<<dp[i]<<endl;
    for(int i=0;i<n+1;i++)
        ans=max(ans,dp[i]);
    cout<<ans<<endl;
}

解决方案:

这里的问题是,虽然你确实会处理每一条边,但你处理它们的顺序并不能保证你真的会发现你想要的路径。例如,考虑这个DAG。

1 -> 2 -> 3

想象一下,输入文件的边缘是按这个顺序排列的。

2 3
1 2

最初,dp[1],dp[2],dp[3]都是零。看到第一行之后,dp[2]被设置为1,第二行之后dp[1]也被设置为1。但是,这些最终的值是不正确的,因为dp[2]应该是2。

这样做失败的原因是,你正在看的dp解决方案只有在你按照拓扑顺序访问边缘时才会起作用,在这种情况下,每次看到从x到y的边缘时,你都知道在考虑更新y之前,你已经计算出了到x的最长路径的长度。

为了解决这个问题,将你读到的边存储在节点的拓扑顺序中,并访问这些边。你可以用很多方法找到拓扑顺序,细节我就不多说了。:-)

希望能帮到你!

给TA打赏
共{{data.count}}人
人已打赏
未分类

如何在android系统中使用菜单项实现对收藏夹按钮的添加和删除。

2022-9-8 17:25:20

未分类

QCursor设置光标颜色时遇到的问题

2022-9-8 17:36:16

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索