记录编号	173548	评测结果	AAAAAAAAAAAAA
题目名称	间谍网络	最终得分	100
用户昵称	<蒟蒻>我要喝豆奶	是否通过	通过
代码语言	C++	运行时间	0.022 s
提交时间	2015-07-29 09:20:44	内存使用	0.75 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<stack>
using namespace std;
const int maxn=3010,Max=0x7fffffff/3;
int n,p,m,x,y,c[maxn],first[maxn],next[maxn*10],u[maxn*10],v[maxn*10],dfs_clock,scc_cnt;
int sccno[maxn],pre[maxn],lowlink[maxn],ru[maxn],min_[maxn],mins[maxn];
stack<int>s;
void dfs(int u){
	pre[u]=lowlink[u]=++dfs_clock;s.push(u);
	for(int i=first[u];i;i=next[i]){
		int k=v[i];
		if(!pre[k]){dfs(k);lowlink[u]=min(lowlink[k],lowlink[u]);}
		else if(!sccno[k])lowlink[u]=min(lowlink[u],pre[k]);
	}
	if(lowlink[u]==pre[u]){
		scc_cnt++;
		for(;;){
			int x=s.top();s.pop();
			sccno[x]=scc_cnt;
			mins[sccno[x]]=min(mins[sccno[x]],x);
			if(x==u)return;
		}
	}
}
void find_scc(int n){
	for(int i=1;i<=n;++i)if(!pre[i])dfs(i);
}
int main(){
	freopen("spyweb.in","r",stdin);
	freopen("spyweb.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;++i)min_[i]=c[i]=mins[i]=Max;
	scanf("%d",&p);
	for(int i=1;i<=p;++i){
		scanf("%d%d",&x,&y);c[x]=y;
	}scanf("%d",&m);
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u[i],&v[i]);next[i]=first[u[i]];first[u[i]]=i;
	}
	find_scc(n);
	for(int i=1;i<=n;++i){
		if(min_[sccno[i]]>c[i])min_[sccno[i]]=c[i];
		for(int j=first[i];j;j=next[j]){
			if(sccno[i]!=sccno[v[j]]){
				ru[sccno[v[j]]]++;
			}
		}
	}
	int tot=0;
	for(int i=1;i<=scc_cnt;++i){
		if(ru[i]==0){
			if(min_[i]==Max){
				printf("NO\n");printf("%d\n",mins[i]);return 0;
			}else{
				tot=tot+min_[i];
			}
		}
	}
	printf("YES\n");printf("%d\n",tot);
	return 0;
}