40分求助

回复帖子

@Fee_cle6418 2018-11-09 09:38 回复

RT

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<stack>
#include<map>
#include<queue>
using namespace std;
struct Edge{
    int to,next;
}e[500005],e2[500005];
int n,m,cnt,cnt2,h[100005],h2[100005],sign,dis[100005];
int dfn[100005],low[100005],ins[100005],belong[100005],SCC,rd[100005],p[100005],p2[100005];
map<pair<int,int>,bool>qq;
stack<int>st;
queue<int>Q;
void Add_Edge(int u,int v){
    e[++cnt].to=v;
    e[cnt].next=h[u];
    h[u]=cnt;
}
void Add_Edge2(int u,int v){
    e2[++cnt2].to=v;
    e2[cnt2].next=h[u];
    h2[u]=cnt;
}
void Tarjan(int u){
    dfn[u]=low[u]=++sign;
    st.push(u);
    ins[u]=1;
    for(int i=h[u];i;i=e[i].next){
        if(!dfn[e[i].to]){
            Tarjan(e[i].to);
            low[u]=min(low[u],low[e[i].to]);
        }
        else if(ins[e[i].to]){
            low[u]=min(low[u],dfn[e[i].to]);
        }
    }
    if(low[u]==dfn[u]){
        SCC++;
        int t;
        do {
            t=st.top();
            st.pop();
            ins[t]=0;
            belong[t]=SCC;
            p2[SCC]+=p[t];
        } while(t!=u);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&p[i]);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        Add_Edge(x,y);
    }
    for(int i=1;i<=n;i++)if(!dfn[i])Tarjan(i);
    for(int i=1;i<=n;i++){
        for(int j=h[i];j;j=e[j].next){
            int q=e[j].to;
            if(belong[i]!=belong[q]&&!qq.count(make_pair(belong[i],belong[q])))Add_Edge2(belong[i],belong[q]),qq[make_pair(belong[i],belong[q])]=1,rd[belong[q]]++;
        }
    }
    for(int i=1;i<=SCC;i++){
        if(!rd[i])Q.push(i),dis[i]=p2[i];
    }
    while(!Q.empty()){
        int x=Q.front();
        Q.pop();
        for(int i=h2[x];i;i=e2[i].next){
            int y=e2[i].to;
            dis[y]=max(dis[y],dis[x]+p2[y]);
            if(!(--rd[y]))Q.push(y);
        }
    }
    int ans=0;
    for(int i=1;i<=SCC;i++)ans=max(ans,dis[i]);
    cout<<ans<<endl;
    return 0;
}
@wycero 2018-11-21 23:26 回复

同问

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int n,m;const int maxn=10005;
vector<int> ve[maxn];
vector<int> sd[maxn];
int dq[maxn];
int dq2[maxn];int dp[maxn];
int dfn[maxn],low[maxn],cnt=0;
int colo[maxn];
int sta[maxn];int din=0;
int inq[maxn];
void dfs(int x,int fa){
    int sz=ve[x].size();
    dfn[x]=low[x]=++cnt;
    inq[x]=1;
    sta[++din]=x;
    rep(i,0,sz-1){
        int y=ve[x][i];
        if(dfn[y]&&inq[y]){
            low[x]=min(low[x],dfn[y]);
        }else{
            dfs(y,x);
            low[x]=min(low[x],low[y]);
        }
    }
    if(low[x]==dfn[x]){
        while(din&&sta[din]!=x){
            if(!din)break;
            dq2[x]+=dq[sta[din]];
            inq[sta[din]]=0;
            colo[sta[din--]]=x;
        }
        if(din){
            dq2[x]+=dq[x];
            colo[sta[din--]]=x;
        }
    }else dq2[x]=dq[x];
}
int dfs2(int x){
    if(dp[x]!=0x3f3f3f3f)return dp[x];
    dp[x]=dq2[x];
    int sz=sd[x].size();
    rep(i,0,sz-1)dp[x]=max(dp[x],dfs2(sd[x][i])+dq2[x]);
    return dp[x];
}
int main(){
    scanf("%d%d",&n,&m);
    rep(i,1,n)scanf("%d",dq+i);
    rep(i,1,m){
        int u,v;scanf("%d%d",&u,&v);
        ve[u].push_back(v);
    }
    rep(i,1,n)if(!dfn[i])dfs(i,-1);
    #ifdef LOCAL
    rep(i,1,n)cout<<dfn[i]<<" ";;cout<<endl;
    rep(i,1,n)cout<<low[i]<<" ";;cout<<endl;
    rep(i,1,n)cout<<colo[i]<<" ";;cout<<endl;
    rep(i,1,n)cout<<dq2[i]<<" ";;cout<<endl;
    #endif
    rep(i,1,n){
        int sz=ve[i].size();
        rep(j,0,sz-1)
            if(colo[ve[i][j]]!=colo[i])
                sd[colo[i]].push_back(colo[ve[i][j]]);
    }
    #ifdef LOCAL
    rep(i,1,n)if(colo[i]){
        int sz=sd[i].size();
        rep(j,0,sz-1)cout<<sd[i][j]<<" "<<" ";
        cout<<endl;
    }
    #endif
    int ans=0;
    memset(dp,0x3f,sizeof dp);
    rep(i,1,n)if(colo[i]==i)ans=max(ans,dfs2(i));
    cout<<ans<<endl;
    return 0;
}