题目链接
题目大意：从一个起点开始走，有若干个终点，并保证你肯定至少能到达其中一个，路径是单向的，可能有环，点上有权值，各点权只算一次，问起点到达给定的任意终点所得到的最大值。
题解：缩点+最短路
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int M=500005;#define INF 0x3f3f3f3fint h,w,q[M<<4];//队列 int tp,s[M];//栈 int n,m,t,o,st,P,c[M];//图 int tim,scnt,dfn[M],low[M],col[M],vl[M];//tarjan相关 int head[M],last[M],d[M];//图 bool ins[M],vis[M];struct edge{int to,nex;}e[M*2],p[M*2];void add(int u,int v){e[t].to=v;e[t].nex=head[u];head[u]=t++;}void sert(int u,int v){p[o].to=v;p[o].nex=last[u];last[u]=o++;}inline void up(int &x,int y){x=x<y?y:x;}void tarjan(int x){ int now=0; dfn[x]=low[x]=++tim; s[++tp]=x,ins[x]=true; for(int i=head[x];i!=-1;i=e[i].nex){ int v=e[i].to; if(!dfn[v]){tarjan(v);if(low[v]<low[x]) low[x]=low[v];} else if(ins[v]&&dfn[v]<low[x]) low[x]=dfn[v]; } if(low[x]==dfn[x]){ scnt++; while(x!=now){ now=s[tp];tp--; ins[now]=false;col[now]=scnt;vl[scnt]+=c[now]; } }}void rebuild(){ for(int x=1;x<=n;x++) for(int i=head[x];i!=-1;i=e[i].nex) if(col[x]!=col[e[i].to]) sert(col[x],col[e[i].to]);}void spfa(int s){ h=1,w=1; for(int i=1;i<=scnt;i++) vis[i]=0,d[i]=-INF;//队列里是新编号 d[col[s]]=vl[col[s]];q[w++]=col[s];//这里注意dis[col[s]]不是0 while(h!=w) { int u=q[h];h++;vis[u]=false; for(int i=last[u];i!=-1;i=p[i].nex){ int v=p[i].to; if(d[v]<d[u]+vl[v]){ d[v]=d[u]+vl[v]; if(!vis[v]) vis[v]=true,q[w++]=v; } } }}void work(){ int x,ans=-INF; for(int i=1;i<=P;i++) scanf("%d",&x),up(ans,d[col[x]]); PRintf("%d",ans);} void init(){ int x,y; t=0,memset(head,-1,sizeof(head)); o=0,memset(last,-1,sizeof(last)); scanf("%d%d",&n,&m); while(m--) scanf("%d%d",&x,&y),add(x,y); for(int i=1;i<=n;i++)scanf("%d",&c[i]); for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i); scanf("%d%d",&st,&P); rebuild();spfa(st);}int main(){ init(); work(); return 0;}新闻热点
疑难解答
