比赛 |
聪明的工作员 |
评测结果 |
AWWWAWAAAWAW |
题目名称 |
聪明的推销员 |
最终得分 |
50 |
用户昵称 |
cdcq |
运行时间 |
0.007 s |
代码语言 |
C++ |
内存使用 |
0.57 MiB |
提交时间 |
2017-03-21 19:28:21 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int oo=168430090;
int rd(){int z=0,mk=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')mk=-1; ch=getchar();}
while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0'; ch=getchar();}
return z*mk;
}
struct ddd{int nxt,y;}e[8100]; int lk[3100],ltp=0;
inline void ist(int x,int y){ e[++ltp].nxt=lk[x],lk[x]=ltp,e[ltp].y=y;}
ddd owo[8100]; int ovo[3100],ouo=0; int oxo[3100];
inline void ono(int x,int y){ owo[++ouo].nxt=ovo[x],ovo[x]=ouo,owo[ouo].y=y;}
int n,m,h,a[3100],b[3100];
int ans=0;
int dfn[3100],low[3100],dfncnt=0;
int grp[3100],grpcnt=0;
int stck[3100],tp=0; bool vstd[3100];
int cst[3100];
bool quq[3100],qaq[3100];
int qwq[3100];
void tj(int x,int y){
dfn[x]=low[x]=++dfncnt; stck[++tp]=x,vstd[x]=true;
for(int i=lk[x];i;i=e[i].nxt)if(e[i].y!=y){
if(!dfn[e[i].y]){
tj(e[i].y,x);
low[x]=min(low[x],low[e[i].y]);
}
else if(vstd[e[i].y]) low[x]=min(low[x],dfn[e[i].y]);
}
if(dfn[x]==low[x]){
cst[++grpcnt]=qwq[grpcnt]=oo; int tmp=0;
while(tmp!=x){
tmp=stck[tp--],vstd[tmp]=false,grp[tmp]=grpcnt;
cst[grpcnt]=min(cst[grpcnt],a[tmp]);
quq[grpcnt]|=qaq[tmp];
qwq[grpcnt]=min(qwq[grpcnt],tmp);
}
}
}
int main(){
//freopen("ddd.in","r",stdin);
freopen("salenet.in","r",stdin);
freopen("salenet.out","w",stdout);
memset(dfn,0,sizeof(dfn));
memset(vstd,0,sizeof(vstd));
memset(a,10,sizeof(a));
memset(quq,0,sizeof(quq));
memset(qaq,0,sizeof(qaq));
cin>>n>>m;
for(int i=1;i<=m;++i) b[i]=rd(),a[i]=rd(),qaq[b[i]]=true;
cin>>h;
int l,r;
while(h--) l=rd(),r=rd(),ist(l,r);
for(int i=1;i<=n;++i)if(!dfn[i]) tj(i,0);
for(int i=1;i<=n;++i)for(int j=lk[i];j;j=e[j].nxt)if(grp[i]!=grp[e[j].y])
ono(grp[i],grp[e[j].y]),++oxo[grp[e[j].y]];
int bwl=0;
for(int i=1;i<=grpcnt;++i){
if(!quq[i] && !oxo[i]){
cout<<"NO"<<endl<<qwq[i]<<endl;
return 0;
}
else if(!oxo[i]) bwl+=cst[i];
}
cout<<"YES"<<endl<<bwl<<endl;
return 0;
}