比赛 聪明的工作员 评测结果 AAWWAWWWWAAW
题目名称 聪明的推销员 最终得分 41
用户昵称 FFF团 运行时间 0.199 s
代码语言 C++ 内存使用 34.79 MiB
提交时间 2017-03-21 20:10:21
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[3000+5][3000+5];
int n,p,r,ans;
bool f=true;
bool vis[3000];


struct per{
	int n;
	int cos;
};

per pe[3000+5];



void dfs(int x){
	for(int i=1;i<=n;i++){
		if(!vis[i]&&a[x][i]==1){
			vis[i]=1;
			dfs(i);
		}
	}
	return;
}

bool cmpp(per x,per y){
	return x.cos<y.cos;
};


int main(){
	freopen("salenet.in","r",stdin);
	freopen("salenet.out","w",stdout);
	cin>>n>>p;
	for(int i=1;i<=p;i++){
		int x,y;
		cin>>x>>y;
		pe[i].n=x;
		pe[i].cos=y ;
	};
	sort(pe+1,pe+p+1,cmpp);
	//for(int i=1;i<=p;i++)cout<<pe[i].n<<" "<<pe[i].cost<<" "<<endl;
	cin>>r;
	for(int i=1;i<=r;i++){
		int x,y;
		cin>>x>>y;
		a[x][y]=1;
	}
	for(int i=1;i<=p;i++){
		if(!vis[pe[i].n]){
			vis[pe[i].n]=1;
			dfs(pe[i].n);
			ans+=pe[i].cos;
		}
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			f=false;
			ans=i;
			break;
		}
	}
	if(f==true)cout<<"YES"<<endl<<ans<<endl;
	else cout<<"NO"<<endl<<ans<<endl;
	fclose(stdin);
	fclose(stdout);
	return 0;
}