比赛 |
聪明的工作员 |
评测结果 |
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;
}