题：https://www.cometoj.com/problem/0461

分析：求边双，最后求多汇点最长路

#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>#include<vector>#include<queue>#define pb push_backusing namespace std;const int M=5e5+5;int sum[M],book[M],jiu[M],head[M],dfn[M],low[M],vis[M],sta[M],cmp[M],dis[M],val[M],newval[M],tot,top,cnt,num;vector<int>g[M];struct node{ int v,w,nextt;}e[M];void tarjan(int u,int f){ dfn[u]=low[u]=++cnt; sta[++top]=u; vis[u]=1; for(int i=0;i<g[u].size();i++){ int v=g[u][i]; if(v==f) continue; if(!dfn[v]){ tarjan(v,u); low[u]=min(low[u],low[v]); } else if(vis[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]){ cmp[u]=++tot; int countt=val[u]; vis[u]=0; int len=top; while(sta[top]!=u){ countt+=val[sta[top]]; cmp[sta[top]]=tot; vis[sta[top--]]=0; } top--; sum[tot]=len-top; newval[tot]=countt; }}void addedge(int u,int v,int w){ e[num].v=v; e[num].w=w; e[num].nextt=head[u]; head[u]=num++;}int spfa(int s,int t){ for(int i=s;i<=t;i++) dis[i]=0,vis[i]=0; queue<int>que; que.push(s); while(!que.empty()){ int u=que.front(); que.pop(); vis[u]=0; for(int i=head[u];~i;i=e[i].nextt){ int v=e[i].v; if(dis[v]<dis[u]+e[i].w){ dis[v]=dis[u]+e[i].w; if(!vis[v]) vis[v]=1,que.push(v); } } } return dis[t];}int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=0;i<=n;i++) head[i]=-1; for(int i=1,u,v;i<=m;i++){ scanf("%d%d",&u,&v); g[u].pb(v); } for(int i=1;i<=n;i++) scanf("%d",&val[i]); int s,p; scanf("%d%d",&s,&p); for(int i=1;i<=p;i++) scanf("%d",&jiu[i]); for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,-1); s=cmp[s]; int t=tot+1; for(int i=1;i<=n;i++) for(int j=0,v;j<g[i].size();j++){ v=g[i][j]; if(cmp[i]!=cmp[v]){ //m cout<<cmp[i]<<"!!!!!"<<cmp[v]<<"!!!!"<<newval[cmp[i]]<<endl; addedge(cmp[i],cmp[v],newval[cmp[i]]); } } for(int i=1;i<=p;i++){ if(book[cmp[jiu[i]]]==1) continue; book[cmp[jiu[i]]]=1; int w=newval[cmp[jiu[i]]]; // if(sum[cmp[jiu[i]]]>1) // w=0; // cout<<cmp[jiu[i]]<<"!!!!!"<<t<<"!!!!"<<w<<endl; addedge(cmp[jiu[i]],t,w); } printf("%d\n",spfa(s,t));}

View Code