比赛 20120709 评测结果 WAWWAAWWWWWW
题目名称 聪明的推销员 最终得分 25
用户昵称 kaaala 运行时间 0.040 s
代码语言 C++ 内存使用 0.44 MiB
提交时间 2012-07-09 10:24:42
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<set>
#include<stack>

using namespace std;

const int oo=~0u>>2;

struct edge
{
	int t;
	edge *next;
	edge(int _t,edge *_next):t(_t),next(_next){}
}*Map[3010];

int N,P,R,dfn[3010],low[3010],ind,tot,ans,ansid=oo,ti[3010];
bool vis[3010],flag[3010];
set<pair<int,int> >tree[3010];
stack<int>s;

bool operator <(pair<int,int>a,pair<int,int>b)
{
	if(a.first<b.first||a.first==b.first&&a.second<b.second)
		return 1;
	return -1;
}

void addedge(int s,int t)
{
	Map[s]=new edge(t,Map[s]);
}

void tarjan(int u)
{
	dfn[u]=low[u]=++ind;
	s.push(u);
	vis[u]=true;
	for(edge *p=Map[u];p;p=p->next)
	{
		int t=p->t;
		if(!dfn[t])
		{
			tarjan(t);
			low[u]=min(low[u],low[t]);
		}
		else if(vis[t])
			low[u]=min(low[u],dfn[u]);
	}
	if(dfn[u]==low[u])
	{
		int t;
		tot++;
		do{
			t=s.top();
			s.pop();
			vis[t]=false;
			tree[tot].insert(make_pair(ti[t],t));
		}while(u!=t);
	}
}

int main()
{
	freopen("salenet.in","r",stdin);
	freopen("salenet.out","w",stdout);
	scanf("%d\n%d",&N,&P);
	for(int i=1;i<=P;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		ti[a]=b;
		flag[a]=true;
	}
	for(int i=1;i<=N;i++)
		if(!flag[i])
			ti[i]=oo;
	scanf("%d",&R);
	for(int i=1;i<=R;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		addedge(a,b);
	}
	for(int i=1;i<=N;i++)
		if(!dfn[i])
			tarjan(i);
	bool f=false;
	for(int i=1;i<=tot;i++)
fl:		if(tree[i].begin()->first==oo)
		{
			for(int j=1;j<=N;j++)
				if(flag[j])
					for(edge *p=Map[j];p;p=p->next)
					{
						int t=p->t;
						if(t==tree[i].begin()->second)
						{
							i++;
							goto fl;
						}
					}
			f=true;
			ansid=min(ansid,tree[i].begin()->second);
		}
		else 
			ans+=tree[i].begin()->first;
	if(f)
		printf("NO\n%d\n",ansid);
	else
		printf("YES\n%d\n",ans);
	return 0;
}