记录编号	39365	评测结果	AAAAAAAAAAAA
题目名称	聪明的推销员	最终得分	100
用户昵称	CC	是否通过	通过
代码语言	C++	运行时间	0.265 s
提交时间	2012-07-09 16:27:56	内存使用	0.52 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
const int INF = 1000000000,end = 3049;
struct edge {
	int y;
	edge *next,*opt;
	edge (int y,edge *next): y(y),next(next) {};
}*a[3050];
int n,m,R,ans,top,bcnt,dindex;
int t[3050],g[3050],tt[3050];
int dfn[3050],low[3050],belong[3050],stack[30000],w[3050];
bool ok[3050],instack[3050];
void bfs(int u) {
	int q[100000] = {0},head = 0,tail = 0;
	q[0] = u;ok[u] = 1;
	while (head <= tail) {
		int now = q[head++];
		for (edge *p = a[now];p;p = p->next) 
			if (!ok[p->y]) 
				ok[q[++tail] = p->y] = 1;
	}
}
void tarjan(int i) {
	int j;
	dfn[i] = low[i] = ++dindex;
	instack[i] = 1;
	stack[++top] = i;
	for (edge *p = a[i];p;p = p->next) {
		j = p->y;
		if (!dfn[j]) {
			tarjan(j);
				if (low[j] < low[i]) low[i] = low[j];
		} else if (instack[j] && dfn[j] < low[i]) 
			low[i] = dfn[j];
	}
	if (dfn[i] == low[i]) {
		bcnt++;
		do {
			j = stack[top--];
			instack[j] = 0;
			belong[j] = bcnt;
		} while (j != i);
	}
}

void solve() {
	top = bcnt = dindex = 0;
	memset(dfn,0,sizeof(dfn));
	for (int i = 1;i <= n;i++) 
		if (!dfn[i]) 
			tarjan(i);
	for (int i = 1;i <= bcnt;i++) tt[i] = INF;
	for (int i = 1;i <= n;i++) {
		if (t[i]) tt[belong[i]] = std::min(tt[belong[i]],t[i]);
		for (edge *p = a[i];p;p = p->next)
			if (belong[i] != belong[p->y]) 
				g[belong[p->y]]++;
	}
	for (int i = 1;i <= bcnt;i++) 
		if (!g[i]) {
			if (tt[i]) ans += tt[i];
		}
}

int main() {
	freopen("salenet.in","r",stdin);
	freopen("salenet.out","w",stdout);
	scanf("%d", &n);
	int p,q;
	scanf("%d", &R);
	for (int i = 1;i <= R;i++) {
		scanf("%d%d", &p, &q);
		w[++w[0]] = p;
		t[p] = q;
	}
	scanf("%d", &m);
	for (int i = 1;i <= m;i++) {
		scanf("%d%d", &p, &q);
		a[p] = new edge(q,a[p]);
	}
	for (int i = 1;i <= w[0];i++) 
		bfs(w[i]);
	for (int i = 1;i <= n;i++) if (!ok[i]) {
		printf("NO\n%d",i);
		return 0;
	}
	solve();
	printf("YES\n%d", ans);
	return 0;
}