题目链接 POJ3249
题意
给定几个带点权有向无环图，选一条从入度为0的起点走到出度为0的终点的路径，使得路径上的点权和最大。
分析
首先点权图转边权图
直接对每条边赋值，值为终点的点权值。
没有入度的点，添加一个顶点，连接一条有向边，使之边权等于该点点权。
多个没有入度的点，只需添加一个顶点并与所有没有入度的点相连即可。
然后求源点到终点的最远路径，使用拓扑排序，然后按排序后的序列更新最远路径。
坑点：
求的不是最短路而是最长路
最远路径超int，要用LL
代码
#include <cstdio> #include <cstring> #include <vector> #include <queue> #include <map> #include <cmath> #include <iostream> #include <algorithm> #define MAX 1000007 #define MAXN 100007 #define MAXM 2000007 #define MOD 1000000007 using namespace std; typedef long long LL; struct Edge{ int to; int w; int next; }edge[MAXM]; int head[MAXN],tot,indegree[MAXN], n,m,s,pw[MAXN],outdegree[MAXN]; LL dist[MAXN],ans; void addEdge(int u,int v,int w){ edge[tot].to=v; edge[tot].next=head[u]; edge[tot].w=w; head[u]=tot++; indegree[v]++; outdegree[u]++; } void topo(){ int q[MAXN],iq=0; for(int i=0;i<=n;i++){ if(indegree[i]==0) q[iq++]=i; } for(int i=0;i<iq;i++){ for(int k=head[q[i]];k!=-1;k=edge[k].next){ int t=edge[k].to; indegree[t]--; if(indegree[t]==0) q[iq++]=t; } } //cout<<iq<<endl; memset(dist, 0xc0,sizeof dist); //for(int i=0;i<MAXN;i++) dist[i]=-100000000000000; //cout<<dist[0]<<endl; dist[s]=0; for(int i=0;i<iq;i++){ for(int k=head[q[i]];k!=-1;k=edge[k].next){ int t=edge[k].to; dist[t]=max(dist[t], dist[q[i]]+edge[k].w); //cout<<dist[t]<<endl; } } } void init(){ memset(head,-1,sizeof head); memset(indegree,0,sizeof indegree); memset(outdegree,0,sizeof outdegree); ans=0xc0c0c0c0c0c0c0c0; tot=0; } int main(){ int u,v,w,q,x; while(scanf("%d%d",&n,&m)==2){ init(); for(int i=1;i<=n;i++){ scanf("%d", &pw[i]); } for(int i=1;i<=m;i++){ scanf("%d%d",&u,&v); addEdge(u, v, pw[v]); } for(int i=1;i<=n;i++){ if(indegree[i]==0){ addEdge(0,i,pw[i]); } } s=0; topo(); for(int i=1;i<=n;i++){ if(outdegree[i]==0){ ans=max(ans, dist[i]); } } printf("%lldn", ans); } return 0; }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
