记录编号	62751	评测结果	AAAAAAAAAAAA
题目名称	聪明的推销员	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.005 s
提交时间	2013-07-09 13:26:16	内存使用	11.79 MiB

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cmath>
using namespace std;
const int SIZEN=3001;
vector<int> c[SIZEN];
vector<int> cust;//顾客
bool cp[SIZEN]={0};//每个人是否可被说服
int tc[SIZEN]={0};//说服每个人需要的时间
bool con[SIZEN][SIZEN]={0};//连通性
int n,m,p;
bool visited[SIZEN]={0};
bool visit[SIZEN]={0};
int ans=0;
void slove(void){
	int i,j,x,u;
	for(i=1;i<=n;i++){
		if(!visited[i]){
			printf("NO\n%d\n",i);
			return;
		}
	}
	printf("YES\n");
	bool col[SIZEN]={0};
	for(i=1;i<=n;i++) col[i]=true;
	for(i=0;i<cust.size();i++){
		x=cust[i];
		for(j=i+1;j<cust.size();j++){
			u=cust[j];
			if(con[u][x]){
				col[x]=false;
				break;
			}
		}
		if(!col[x]) ans-=tc[x];//不选
		else{
			for(j=1;j<=n;j++){
				if(con[x][j]) col[j]=false;
			}
		}
	}
	printf("%d\n",ans);
}
bool cmp(int a,int b){
	return tc[a]>tc[b];
}
void DFS(int x,int grand){
	if(visit[x]) return;
	visited[x]=true;
	con[grand][x]=true;
	visit[x]=true;
	int i,u;
	for(i=0;i<c[x].size();i++){
		u=c[x][i];
		DFS(u,grand);
	}
}
void travel(void){
	int i;
	for(i=1;i<=n;i++){
		if(cp[i]){
			memset(visit,0,sizeof(visit));
			DFS(i,i);
		}
	}
}
void read(void){
	memset(tc,15,sizeof(tc));
	scanf("%d%d",&n,&p);
	int i,x;
	for(i=1;i<=p;i++){
		scanf("%d",&x);
		cp[x]=true;
		cust.push_back(x);
		scanf("%d",&tc[x]);
		ans+=tc[x];
	}
	scanf("%d",&m);
	int a,b;
	for(i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		c[a].push_back(b);
	}
}
int main(){
	freopen("salenet.in","r",stdin);
	freopen("salenet.out","w",stdout);
	read();
	travel();
	sort(cust.begin(),cust.end(),cmp);
	//之后cust中按说服时间降序
	slove();
	return 0;
}