poj3249 拓扑排序+DP

题意：给出一个有向无环图，每个顶点都有一个权值。求一条从入度为0的顶点到出度为0的顶点的一条路径，路径上所有顶点权值和最大。

思路：因为是无环图，则对于每个点经过的路径求其最大权值有，dp[i]=max(dp[j]) j为i的子节点集合。再根据其要求入度为零为顶点，可以用拓扑排序每次枚举入度为零的点删去找下一个入度为零的点进行dp。

代码：

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

#define MAXN 100005

#define MAXM 1000005

#define inf 100000000

int n,m,tot,ans;

int indegree[MAXN],outdegree[MAXN],vis[MAXN],dp[MAXN],head[MAXN],cost[MAXN];

struct Edge

{

    int from,to,next;

}edge[MAXM];

void addedge(int v,int w)

{

    edge[tot].from=v;

    edge[tot].to=w;

    edge[tot].next=head[v];

    head[v]=tot++;

}

void Topo_dp()

{

    int c=1;

    while(c<n)

    {

        for(int i=1;i<=n;i++)

        {

            if(!indegree[i]&&!vis[i])

            {

                vis[i]=true;

                c++;

                for(int j=head[i];j!=-1;j=edge[j].next)

                {

                    int v=edge[j].to;

                    indegree[v]--;

                    if(dp[i]+cost[v]>dp[v])

                    {

                        dp[v]=dp[i]+cost[v];

                    }

                }

            }

        }

    }

}

int main()

{

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        for(int i=1;i<=n;i++)

        {

            scanf("%d",&cost[i]);

        }

        for(int i=1;i<=n;i++)

        {

            indegree[i]=0;

            outdegree[i]=0;

            vis[i]=false;

        }

        tot=1;

        memset(head,-1,sizeof(head));

        for(int i=1;i<=m;i++)

        {

            int v,w;

            scanf("%d%d",&v,&w);

            addedge(v,w);

            indegree[w]++;

            outdegree[v]++;

        }

        ans=-inf;

        for(int i=1;i<=n;i++)

        {

            if(!indegree[i])

            {

                dp[i]=cost[i];

            }

            else

            {

                dp[i]=-inf;

            }

        }

        Topo_dp();

        for(int i=1;i<=n;i++)

        {

            if(!outdegree[i]&&dp[i]>ans)

                ans=dp[i];

        }

        printf("%d\n",ans);

    }

    return 0;

}

巴特西

poj3249 拓扑排序+DP

最新文章

热门文章