hack WA 了求条
查看原帖
hack WA 了求条
578029
ivyjiao楼主2024/8/1 21:00

rt,输出 NO 2

#include<bits/stdc++.h>
using namespace std;
int n,m,c,num,mon,a[100001],u,v,col[100001],cnt,rd[100001],sum[100001],b[100001],l,ans,dfn;
vector<int>G[100001],H[100001],I[100001],s;
queue<int>q;
bool vis[100001],cs[100001],vis2[100001];
void dfs1(int u){
    vis[u]=1;
    for(int i=0;i<G[u].size();i++) if(!vis[G[u][i]]) dfs1(G[u][i]);
    s.push_back(u);
}
void dfs2(int u){
    col[u]=cnt;
    if(a[u]){
        cs[cnt]=1;
        sum[cnt]=min(sum[cnt],a[u]);
    }
    for(int i=0;i<H[u].size();i++) if(!col[H[u][i]]) dfs2(H[u][i]);
}
void kosaraju(){
    for(int i=1;i<=n;i++) if(!vis[i]) dfs1(i);
    for(int i=s.size()-1;i>=0;i--){
        if(!col[s[i]]){
            cnt++;
            dfs2(s[i]);
        }
    }
}
void dfs(int u){
    ++dfn; 
    vis2[u]=1; 
    for(int i=0;i<I[u].size();i++){
        if(vis2[I[u][i]]) continue; 
        dfs(I[u][i]); 
    }
}
void topo(){
    for(int i=1;i<=cnt;i++){
        if(!rd[i]) q.push(i);
    }
    while(q.size()){
        u=q.front();
        q.pop();
        if(cs[u]) b[++l]=u;
        for(int i=0;i<I[u].size();i++){
            rd[I[u][i]]--;
            if(!rd[I[u][i]]) q.push(I[u][i]); 
        }
    }
}
int main(){
    memset(sum,0x3f,sizeof sum);
    cin>>n>>c;
    for(int i=1;i<=c;i++){
        cin>>num>>mon;
        a[num]=mon;
        cs[num]=1;
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        G[u].push_back(v);
        H[v].push_back(u);
    }
    kosaraju();
	for(int i=1;i<=n;i++){
		for(int j=0;j<G[i].size();j++){
			if(col[i]!=col[G[i][j]]){
                rd[col[G[i][j]]]++;
                I[col[i]].push_back(col[G[i][j]]);
            }
        }
    }
    topo();
    for(int i=1;i<=l;i++){
        if(!vis2[b[i]]){
            ans+=sum[b[i]];
            dfs(b[i]); 
        }
    }
    if(dfn==cnt) cout<<"YES\n"<<ans;
    else{
        cout<<"NO\n";
        for(int i=1;i<=n;i++){
            if(!vis2[col[i]]){
                cout<<i;
                return 0;
            }
        }
    }
}
2024/8/1 21:00
加载中...