LOJ-10096（强连通+bfs）

题目链接：传送门

思路：

强连通缩点，重建图，然后广搜找最长路径。

#include
#include
#include
#include
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 xx: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]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;
}

转载于:https://www.cnblogs.com/2018zxy/p/10370064.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！