比赛 20120709 评测结果 AAAWAAAAAAAW
题目名称 聪明的推销员 最终得分 83
用户昵称 Citron酱 运行时间 0.027 s
代码语言 C++ 内存使用 0.42 MiB
提交时间 2012-07-09 09:34:22
显示代码纯文本
#include <cstdio>
#include <climits>

#define I_F "salenet.in"
#define O_F "salenet.out"

const int MAXn=3000;
const int MAXm=8000+1;

struct edge
{
	int x;
	edge *next;
};

int n, p;
edge pool[MAXm];
edge *ph=pool;
edge *map[MAXn]={NULL};
int c[MAXn];
int s[MAXn];
int d[MAXn]={0}, l[MAXn]={0}, index=0;
int st[MAXn];
int top=0;
short f[MAXn];
long ans=0;
bool flag=true;

void Input();
void Tarjan(const int&);
inline int Min(const int&, const int&);
void Dfs(const int&);
void Search();
void Output();

int main()
{
	Input();
	Search();
	Output();
	return 0;
}

void Input()
{
	int m, a;
	edge *temp;
	freopen(I_F,"r",stdin);
	scanf("%d%d",&n,&p);
	for (int i=0; i<n; ++i)
		c[i]=INT_MAX;
	for (int i=0; i<p; ++i)
	{
		scanf("%d",&a);
		scanf("%d",&c[a-1]);
	}
	for (scanf("%d",&m); m>0; --m)
	{
		scanf("%d",&a);
		temp=map[--a];
		map[a]=ph++;
		scanf("%d",&(map[a]->x));
		--map[a]->x;
		map[a]->next=temp;
	}
}

void Tarjan(const int &x)
{
	d[x]=l[x]=++index;
	f[x]=1;
	st[top++]=x;
	for (edge *i=map[x]; i!=NULL; i=i->next)
		if (f[i->x]==0)
		{
			Tarjan(i->x);
			l[x]=Min(l[x],l[i->x]);
		}
		else if (f[i->x]==1)
			l[x]=Min(l[x],d[i->x]);
	if (d[x]==l[x])
	{
		int v;
		do
		{
			v=st[--top];
			s[v]=x;
		} while (v!=x);
	}
}

inline int Min(const int &a, const int &b)
{
	return (a<b)?a:b;
}

void Dfs(const int &x)
{
	f[x]=1;
	for (edge *i=map[x]; i!=NULL; i=i->next)
		if (f[i->x]==0)
			Dfs(i->x);
}

void Search()
{
	int m[MAXn];
	for (int i=0; i<n; ++i)
		f[i]=0,
		s[i]=i;
	for (int i=0; i<n; ++i)
		if (f[i])
			Tarjan(i);
	for (int i=0; i<n; ++i)
		f[i]=0,
		m[i]=INT_MAX;
	for (int i=0; i<n; ++i)
		m[s[i]]=Min(m[s[i]],c[i]);
	for (int i=0; i<n; ++i)
		if (f[i]==0 && m[s[i]]<INT_MAX)
			Dfs(i),
			ans+=m[s[i]];
	for (int i=0; i<n; ++i)
		if (f[i]==0)
		{
			ans=i+1;
			flag=false;
			break;
		}
}

void Output()
{
	freopen(O_F,"w",stdout);
	if (flag)
		printf("YES\n%ld\n",ans);
	else
		printf("NO\n%ld\n",ans);
}