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