rt/kk

刚学tarjan，参照第一篇题解搞得，样例1不知道为啥总是输出INF，提交三十多分/tuu

感谢巨佬们，会有微小的小号关注/kel

#include<bits/stdc++.h>
#define reg register int
#define INF (1<<30)
#define pb push_back
#define vc vector
#define fst first
#define scd second
//#define int long long
#define rep(i,x,y) for(int i=x;i<=y;i++)
using namespace std;
int read(){
	int res=0,fs=1; char c=getchar();
	while(!(c>='0' && c<='9')){ if(c=='-')fs=-1; c=getchar(); }
	while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
	return res*fs;
}
void print(int x){
    if(x<0) { putchar('-'); x=-x;}
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
int n,cnt,m,ans,tmp,k;
typedef pair<int,int> P;
//struct PROBLEM_SOLVER{
//	   int n,m;
//}solver;

//signed main(){
int f[100050];
struct node{
	int u,v,w;
}a[1000005]; 
vector<int>G[100005];
int vis[10005],r; 
int path[3005];
int ru[100005];  
	int dfn[1000005],low[100005],tong[1000005];
	int sum[1000005];
	int tim=0; 
	// stack<int>stk;
	int top=0,stk[100005];
	int kid[100005];
	void tarjan(int x){
		// if(dfn[x]) return ;
		// cout<<"TARJAN:"<<x<<endl;
		// stk.push(x);
		top++;
		stk[top]=x;
		tong[x]=1;
		tim++;
		dfn[x]=low[x]=tim;
		for(int i=0;i<G[x].size();i++){
			int u=x,v=G[x][i];
			if(!dfn[v]){
				// cout<<"\t to "<<v<<endl;
				tarjan(v);
				low[x]=min(low[x],low[v]);
			}else{
				if(tong[v]) low[x]=min(low[x],dfn[v]);
			}
		}
		if(dfn[x]==low[x]){ 
			cnt++; 
			// cout<<"#"<<cnt<<":\n";
			// cout<<"\t"<<stk[1]<<' '<<stk[2]<<endl; 
			while(stk[top+1]!=x){ 
			// cout<<"\t\t ok\n";
				sum[cnt]=min(sum[cnt],f[stk[top]]); 
				kid[stk[top]]=cnt; 
				tong[stk[top]]=0; 
				top--;
			} 
		}
	}
	void sol1(){ 
		memset(sum,0x3f,sizeof(sum));
		rep(i,1,n){
			if(!dfn[i]&&f[i]<=100000000) {
				tarjan(i);
			}
		}
		rep(i,1,n){
			if(!dfn[i]){
				cout<<"NO\n"<<i;
				return ;
			}
		}
		rep(i,1,n){
			for(int j=0;j<G[i].size();j++){
				int u=i,v=G[i][j];
				if(kid[u]!=kid[v]){
					ru[v]++;
				}
			}
		}
		rep(i,1,cnt){
			if(ru[i]==0) ans+=sum[i];
		}
		cout<<"YES\n"<<ans;
	} 
int main() { 
	cin>>n>>k;
	memset(f,0x3f,sizeof(f));
	// f[0]=0;
	rep(i,1,k){
		int idx,x;
		cin>>idx>>x;
		
		f[idx]=x;
	}
	// rep(i,1,n) xuyao[i]=1;
	cin>>r;
	rep(i,1,r){
		cin>>a[i].u>>a[i].v;
		G[a[i].u].pb(a[i].v); 
	}
	sol1();
    return 0;
}