记录编号	408351	评测结果	AAAAAAAAAAAA
题目名称	聪明的推销员	最终得分	100
用户昵称	TARDIS	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2017-05-24 15:20:57	内存使用	0.00 MiB

#include<bits/stdc++.h>
#define COGS
using namespace std;
const int maxn=3010;
int n,m,p,money[maxn],dfn[maxn],low[maxn],temp,a,b,dfs_clock,scc_cnt,belong[maxn];
int am[maxn]={0},inde[maxn],outde[maxn];
bool instack[maxn],good[maxn];
stack<int> st;
vector<int> G[maxn];
vector<int> T[maxn];
inline void in(){
	#ifdef COGS
	freopen("salenet.in","r",stdin);
	freopen("salenet.out","w",stdout);
	#endif
	scanf("%d%d",&n,&p);
	for (int i=1;i<=p;i++){
		scanf("%d",&temp);
		good[temp]=1;
		scanf("%d",&money[temp]);
	}
	scanf("%d",&m);
	for (int i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		G[a].push_back(b);
	}
}
inline void dfs(int now){
	if (dfn[now]) return;
	dfs_clock++;
	low[now]=dfn[now]=dfs_clock;
	st.push(now);instack[now]=1;
	int num=G[now].size();
	for (int i=0;i<num;i++){
		int to=G[now][i];
		if (!dfn[to]){
			dfs(to);
			low[now]=min(low[now],low[to]);
		}
		else if (instack[to]){
			low[now]=min(low[now],dfn[to]);
		}
	}
	if (low[now]==dfn[now]){
		scc_cnt++;int j;bool use=0;
		int temp=1e9;
		do{
			j=st.top();
			st.pop();instack[j]=0;
			belong[j]=scc_cnt;
			if (good[j]) {temp=min(temp,money[j]);use=1;}
		}while(j!=now);
		if(use) am[scc_cnt]=temp;
	}
}
inline void tarjan_bg(){
	for (int i=1;i<=n;i++){
		dfs(i);
	}
	for (int i=1;i<=n;i++){
		int num=G[i].size();
		for (int j=0;j<num;j++){
			int to=G[i][j];
			if (belong[i]!=belong[to]){
				T[belong[i]].push_back(belong[to]);
				inde[belong[to]]++,outde[belong[i]]++;
			}
		}
	}
}
inline void deal(){
	tarjan_bg();
}
inline void pr(){
	int ans=0;bool flag=1;
	for (int i=1;i<=scc_cnt;i++){
		if (flag==0) break;
		if (inde[i]==0){
			if (am[i]){
				ans+=am[i];
			}
			else{
				for (int j=1;j<=n;j++){
					if (belong[j]==i){
						printf("NO\n%d",j);
						flag=0;
					}
				}
			}
		}
	}
	if (flag) printf("YES\n%d",ans);
}
int Main(){
	in();
	deal();
	pr();
	return 0;
}
int main(){;}
int xlm=Main();