題目鏈接：傳送門

思路：

強連通縮點，重建圖，然后廣搜找最長路徑。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 1e6+10; int head[maxn],next[maxn],ver[maxn],tot; int low[maxn],num[maxn],tim,co[maxn],col,si[maxn]; int vis[maxn],dis[maxn]; int st[maxn],top,a[maxn],in[maxn],que[maxn],w,t; int xx[maxn],yy[maxn],nu[maxn],ans,m,n,vv[maxn]; int MIN(int x,int y) {return x<y?x:y; } int MAX(int x,int y) {return x>y?x:y; } void Init() {memset(vis,0,sizeof(vis));memset(in,0,sizeof(in));memset(vv,0,sizeof(vv));top=0;tim=0;tot=0;col=0;w=0;t=0; } void addedge(int u,int v) {ver[++tot]=v;next[tot]=head[u];head[u]=tot; } void Tarjan(int u) {low[u]=num[u]=++tim;st[++top]=u;for(int i=head[u];i;i=next[i]){int v=ver[i];if(!num[v]){Tarjan(v);low[u]=MIN(low[u],low[v]);}else if(!co[v]) low[u]=MIN(low[u],num[v]);}if(low[u]==num[u]){col++;co[u]=col;si[col]=a[u];vv[col]=MAX(vv[col],vis[u]);while(st[top]!=u){co[st[top]]=col;vv[col]=MAX(vv[col],vis[st[top]]);si[col]+=a[st[top]];top--;}top--;} } bool cmp(int x,int y) {if(xx[x]!=xx[y]) return xx[x]<xx[y];else return yy[x]<yy[y]; } void Remove() {memset(head,0,sizeof(head));tot=0;for(int i=1;i<=m;i++){nu[i]=i;xx[i]=co[xx[i]];yy[i]=co[yy[i]];}sort(nu+1,nu+m+1,cmp); } void Build() {for(int i=1;i<=m;i++){int z=nu[i];if(xx[z]!=yy[z]&&(xx[z]!=xx[nu[i-1]]||yy[z]!=yy[nu[i-1]])) addedge(xx[z],yy[z]),in[yy[z]]++;} } int main(void) {int i,j,ss,pp,tp;scanf("%d%d",&n,&m);Init();for(i=1;i<=m;i++){scanf("%d%d",&xx[i],&yy[i]);addedge(xx[i],yy[i]);}for(i=1;i<=n;i++) scanf("%d",&a[i]);scanf("%d%d",&ss,&pp);for(i=1;i<=pp;i++){scanf("%d",&tp);vis[tp]=1;}for(i=1;i<=n;i++)if(!num[i]) Tarjan(i);Remove();Build();que[++w]=co[ss];dis[co[ss]]=si[co[ss]];while(t<w){int u=que[++t];for(i=head[u];i;i=next[i]){int v=ver[i];if(dis[v]<dis[u]+si[v]) dis[v]=dis[u]+si[v],que[++w]=v;}}int mx=0;for(i=1;i<=col;i++)if(vv[i]==1) mx=MAX(mx,dis[i]);printf("%d\n",mx);return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/2018zxy/p/10370064.html

總結(jié)

以上是生活随笔為你收集整理的LOJ-10096（强连通+bfs）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。