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