比赛 聪明的工作员 评测结果 AAAAWAAAAAAA
题目名称 聪明的推销员 最终得分 91
用户昵称 Emine 运行时间 0.350 s
代码语言 C++ 内存使用 8.98 MiB
提交时间 2017-03-21 19:20:56
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int maxn=3005;
int n,p,r;
vector<int> gk;       //顾客数量
vector<int> c[maxn];
bool sf[maxn]={0};    //是否能被说服 
int sj[maxn]={0};     //说服所需时间 
bool qlt[maxn][maxn]; 
int ans=0;

bool dpx(int a,int b)
{
	return sj[a]>sj[b];
}

void read()
{
	memset(sj,1,sizeof(sj));
	scanf("%d%d",&n,&p);
	int x;
	for(int i=1;i<=p;i++)
	{
		scanf("%d",&x);
		sf[x]=1;
		gk.push_back(x);
		scanf("%d",&sj[x]);
		ans+=sj[x];
	}
	scanf("%d",&r);
	int a,b;
	for(int i=1;i<=r;i++)
	{
		scanf("%d%d",&a,&b);
		c[a].push_back(b);
	}
}
bool kg[maxn];        //看过
bool k[maxn];         //看 

void dfs(int x,int y)
{
	if(k[x])
	  return;
	kg[x]=1;
	qlt[y][x]=1;
	k[x]=1;
	int z;
	for(int i=0;i<c[x].size();i++)
	{
		z=c[x][i];
		dfs(z,y);
	}
}

void kyk()             //看一看 
{
	for(int i=1;i<=n;i++)
	{
		if(sf[i])
		{
			memset(k,0,sizeof(k));
			dfs(i,i);
		}
	}
}

int main()
{
	freopen("salenet.in","r",stdin);
	freopen("salenet.out","w",stdout);
	read();
	kyk();
	sort(gk.begin(),gk.end(),dpx);
	int x,z;
	for(int i=1;i<=n;i++)
	{
		if(!kg[i])
		{
			printf("NO\n%d\n",i);
			break;
		}
	}
	printf("YES\n");
	bool cs[maxn]={0};             
	for(int i=1;i<=n;i++) 
	  cs[i]=1;
	for(int i=0;i<gk.size();i++)
	{
		x=gk[i];
		for(int j=i+1;j<gk.size();j++)
		{
			z=gk[j];
			if(qlt[z][x])
			{
				cs[x]=0;
				break;
			}
		}
		if(!cs[x]) 
		  ans-=sj[x];       
		else
		{
			for(int j=1;j<=n;j++)
			{
				if(qlt[x][j]) 
				  cs[j]=0;
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}