记录编号	460632	评测结果	AAAAAAAAAAAA
题目名称	聪明的推销员	最终得分	100
用户昵称	FFF团	是否通过	通过
代码语言	C++	运行时间	0.045 s
提交时间	2017-10-17 20:52:15	内存使用	0.50 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
const int INF=0x7fffffff;
const int maxn=3005;
vector<int>G[maxn];
vector<int>R[maxn];
vector<int>NEW[maxn];
vector<int>scc[maxn];
stack<int>sta;
int n,p,m,cnt,ans;
int cost[maxn],in[maxn],belong[maxn],COST[maxn];
bool vis[maxn];
void dfs1(int x){
	vis[x]=1;
	int l=G[x].size();
	for(register int i=0;i<l;i++){
		int v=G[x][i];
		if(!vis[v])dfs1(v);
	}
	sta.push(x);
}
void dfs2(int x){
	belong[x]=cnt;
	scc[cnt].push_back(x);
	int l=R[x].size();
	for(register int i=0;i<l;i++){
		int v=R[x][i];
		if(!belong[v])dfs2(v);
	}
}
void SCC(){
	for(register int i=1;i<=n;i++)
	if(!vis[i])dfs1(i);
	while(!sta.empty()){
		int u=sta.top();sta.pop();
		if(!belong[u]){
			cnt++;
			dfs2(u);
		}
	}
}
void SCC_S(){
	SCC();
	fill(COST+1,COST+cnt+1,INF);
	for(register int i=1;i<=cnt;i++){
		int l1=scc[i].size();
		fill(vis+1,vis+cnt+1,0);
		for(register int j=0;j<l1;j++){
			int u=scc[i][j],l2=G[u].size();
			for(register int k=0;k<l2;k++){
				int v=G[u][k];
				if(!vis[belong[v]]&&belong[v]!=belong[u]){
					NEW[i].push_back(belong[v]);
					vis[belong[v]]=1;in[belong[v]]++;
				}
			}
			COST[i]=min(COST[i],cost[u]);
		}
	}
}
void read(){
	freopen("salenet.in","r",stdin);
	freopen("salenet.out","w",stdout);
	scanf("%d%d",&n,&p);
	fill(cost+1,cost+n+1,INF);
	int x,y;
	for(register int i=1;i<=p;i++){
		scanf("%d%d",&x,&y);
		cost[x]=y;
	}
	scanf("%d",&m);
	for(register int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		R[y].push_back(x);
	}	
}
void work(){
	bool possible=1;
	fill(vis+1,vis+cnt+1,0);
	queue<int>q;
	for(int i=1;i<=cnt;i++)
	if(!in[i]){
		if(COST[i]==INF)possible=0;
		else {
			ans+=COST[i];
			q.push(i);
			vis[i]=1;
		}
	}
	if(!possible)
	for(int i=1;i<=cnt;i++)
	if(COST[i]!=INF&&!vis[i]){
		q.push(i);
		vis[i]=1;
	}
	while(!q.empty()){
		int u=q.front();q.pop();
		int l=NEW[u].size();
		for(int i=0;i<l;i++){
			int v=NEW[u][i];
			if(!vis[v]){
				q.push(v);
				vis[v]=1;
			}
		}
	}
	if(!possible){
		for(int i=1;i<=n;i++)
		if(!vis[belong[i]]){
			ans=i;
			break;
		}
		printf("NO\n%d",ans);
	}
	else printf("YES\n%d",ans);
}
int main(){
	read();
	SCC_S();
	work();
	return 0;
}