[APIO2009-C]抢掠计划_C

概述题：https://www.cometoj.com/problem/0461 分析：求边双，最后求多汇点最长路 #include<iostream>#include<cstring>#include<algorithm>#include<cstdio>#include<vector>#include<queue>#define pb push_backusing nam

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

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

#include<iostream>#include<cstring>#include<algorithm>#include<cst@R_404_6901@>#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));}