71WA#2#3#4#12
查看原帖
71WA#2#3#4#12
1069816
Tsuki091117楼主2024/7/10 16:16
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3010,M=8010;
int n,p,r,a,b,cnt,ans;
int h[N],e[M],ne[M],idx;
int money[N],mon[N];
bool vis[N],f[N],q[N];
bool l;
int v[N];
int dfn[N],low[N],timestamp;
int stk[N],top;
bool in_stk[N];
int id[N],scc_cnt;
int din[N];
void add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int x){
	cnt++;
	if(cnt==n){
		l=1;
		return;		
	}
	for(int i=h[x];i!=-1;i=ne[i]){
		int j=e[i];
		if(!vis[j]) vis[j]=true,f[j]=1,dfs(j);
//			vis[j]=false;
	}
	return;
}
void tarjan(int u){
	dfn[u]=low[u]=++timestamp;
	stk[++top]=u,in_stk[u]=true;
	for(int i=h[u];i!=-1;i=ne[i]){
		int j=e[i];
		if(!dfn[j]){
			tarjan(j);
			low[u]=min(low[u],low[j]);
		}
		else if(in_stk[j]){
			low[u]=min(low[u],dfn[j]);
		}
	}
	if(dfn[u]==low[u]){
		int y;
	
		bool f=0;
		if(stk[top]!=u){
			f=1;	
			scc_cnt++;
		} 
//		int k=0;
		do{
//			k++;
			y=stk[top--];
			in_stk[y]=false;
//			id[y]=scc_cnt;
//			if(k!=1||y!=u)
			if(f){
				mon[scc_cnt]=min(mon[scc_cnt],money[y]);
			}
//				mon[scc_cnt]=min(mon[scc_cnt],money[y]);
		}while(y!=u);
	}
} 
signed main(){
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
	memset(h,-1,sizeof h);
	memset(mon,0x3f,sizeof mon);
	cin>>n>>p;
	while(p--){
		int x,y;
		cin>>x>>y;
		v[x]=x;
		money[x]=y,vis[x]=true,q[x]=1;
	}
	cin>>r;
	while(r--){
		cin>>a>>b;
		add(a,b);
		v[b]=a;
		din[b]++;
	}
	for(int i=1;i<=n;i++)
		if(vis[i]&&!f[i]) f[i]=1,dfs(i);
	if(l==false){
		cout<<"NO\n";
		for(int i=1;i<=n;i++)
			if(!vis[i]){
				cout<<i;
				break;
			}	
	}
	else{
		cout<<"YES\n";
		for(int i=1;i<=n;i++){
			if(!dfn[i]){
				tarjan(i);
			}
		}
		int ans=0;
		for(int i=1;i<=scc_cnt;i++){
			ans+=mon[i];
		}
		for(int j=1;j<=n;j++){
			if(din[j]==0){
				ans+=money[j];
			}
		}
		cout<<ans;
	}
	return 0;
}
2024/7/10 16:16
加载中...