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

#include<bits/stdc++.h>
using namespace std;
const int max_n=3005;
int n,p,x,iinn[max_n],y,t[max_n],t1[max_n],r,inn[max_n],scc[max_n],scc_cnt,scc_time,pre[max_n],low[max_n];
vector<int>a[max_n];
vector<int>ne[max_n];
stack<int>S;
inline int read()
{
	char ch;
	int a=0;
	ch=getchar();
	while(!('0'<=ch&&'9'>=ch))
	ch=getchar();
	while('0'<=ch&&'9'>=ch)
	a=a*10+ch-'0',
	ch=getchar();
	return a;
}
inline void dfs(int x)
{
	pre[x]=low[x]=++scc_time;
	S.push(x);
	for(int i=0;i<a[x].size();i++)
	{
		int u=a[x][i];
		if(!pre[u])dfs(u),low[x]=min(low[x],low[u]);
		else if(!scc[u])low[x]=min(low[x],pre[u]);
	}
	if(low[x]==pre[x])
	{
		scc_cnt++;
	for(;;)
	{
		int v=S.top();
		S.pop();
		scc[v]=scc_cnt;
		if(v==x)break;
	}
}
}
inline void tar_suo()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<a[i].size();j++)
		{
			int u=a[i][j];
			if(scc[u]!=scc[i])
			ne[scc[i]].push_back(scc[u]),
			inn[scc[u]]++;
		}
	}
}
int main()
{
	freopen("salenet.in","r",stdin);
	freopen("salenet.out","w",stdout);
	n=read();
	p=read();
	for(int i=1;i<=p;i++)
	{
		x=read();
		t[x]=read();
	}
	r=read();
	for(int i=1;i<=r;i++)
	{
		x=read();
		y=read();
		a[x].push_back(y);
		iinn[y]++;
	}
	for(int i=1;i<=n;i++)
	if(!pre[i])dfs(i);
	tar_suo();
	int cnt=0,book=0;
	for(int i=1;i<=scc_cnt;i++)
	{
	if(iinn[i]==0)cnt++;
	if(iinn[i]==0&&!t[i])book=1;
	}
	memset(t1,0x7f,sizeof(t1));
	for(int i=1;i<=n;i++)
	if(t[i])t1[scc[i]]=min(t1[scc[i]],t[i]);
	if(cnt<=p&&!book)
	{
		int ans=0;
		cout<<"YES";
		for(int i=1;i<=scc_cnt;i++)
		if(inn[i]==0)ans+=t1[i];
		cout<<ans;
	}
	else 
	{
		cout<<"NO";
		int k=0;
		for(int i=1;i<=n;i++)
	{	
	if(iinn[i]==0&&!t[i])
	{
		cout<<i;
		break;
	}
		}
	}
	return 0;
}