为啥这代码样例二没过,却全AC。
查看原帖
为啥这代码样例二没过,却全AC。
966082
huangmingyi楼主2024/2/23 16:43
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=20005;
struct node{
    int u,v;
}a[20005];
int dfn[maxn],low[maxn],in[maxn],sum,cnt,scc[maxn],res[maxn],mo[maxn],id[maxn];
bool vis[maxn];
vector<int> nbr[maxn],new_nbr[maxn];
stack<int> s;
void tarjan(int u){
    s.push(u);
    vis[u]=1;
    dfn[u]=low[u]=++cnt;
	for(int i=0;i<nbr[u].size();i++){
        int next=nbr[u][i];
        if(!dfn[next]){
            tarjan(next);
            low[u]=min(low[u],low[next]);
        }else if(vis[next]){
        	low[u]=min(low[u],dfn[next]);
		}
    }
    if(dfn[u]==low[u]){
        sum++;
		vis[u]=0;
        scc[u]=sum;
        res[sum]=mo[u];
        id[sum]=u;
		while(s.top()!=u){
			int cur=s.top();
			s.pop();    
            vis[cur]=0;
            scc[cur]=sum;
            res[sum]=min(res[sum],mo[cur]);
			id[sum]=min(id[sum],cur);
		}
    	s.pop();
	}
    return ;
}
void mark(int cur){
	if(cur==0){
		return ;
	}
	vis[cur]=1;
	for(int nxt : new_nbr[cur]){
		mark(nxt);
	}
	return ;
}
signed main(){
	int n,p,m,pos=0,ans=0;
	memset(mo,0x3f,sizeof(mo));
    cin>>n>>p;
    for(int i=1;i<=p;i++){
		int y,x;
		cin>>y>>x;
		mo[y]=x;
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		a[i]={x,y};
		nbr[x].push_back(y);
	}
	cnt=0;
    for(int i=1;i<=n;i++){
		if(dfn[i]==0){
			tarjan(i);
		}
	}
	for(int i=1;i<=m;i++){
        int fx=scc[a[i].u];
        int fy=scc[a[i].v];
		if(fx!=fy){
			in[fy]++;
			new_nbr[fx].push_back(fy);
		}
	}
    for(int i=1;i<=sum;i++){
		if(!in[i]){
			if(res[i]==0x3f3f3f3f3f3f3f3f){
				pos=n+1;
			}else{
				ans=ans+res[i];
				mark(i);
			}
		}
	}
	if(pos==0){
		cout<<"YES"<<endl;
		cout<<ans;
		return 0;
	}
	cout<<"NO"<<endl;
	for(int i=1;i<=n;i++){
		if(mo[i]==0x3f3f3f3f3f3f3f3f){
			pos=min(pos,id[scc[i]]);
		}
	}
	cout<<pos<<endl;
    return 0;
}
2024/2/23 16:43
加载中...