比赛 20120709 评测结果 TAAAAAAAAATA
题目名称 聪明的推销员 最终得分 83
用户昵称 ZhouHang 运行时间 3.360 s
代码语言 C++ 内存使用 43.52 MiB
提交时间 2012-07-09 10:05:00
显示代码纯文本
/**
*Prob	:	salenet
*Data	: 2012-7-9
*Sol	: 骗分
*/

#include <cstdio>
#include <cstring>
#include <cmath>

#define MaxN 3010
#define oo 200000000

using namespace std;

int in[MaxN];
int n,count;
bool used[MaxN],d[MaxN][MaxN];
int a[MaxN][MaxN],mindis[MaxN];

//dfs判断存在性
void dfs(int x)
{
	used[x] = true; count++;
	for (int i=1; i<=n; i++)
		if (d[x][i]&&!used[i]) dfs(i);
}

//寻找环,返回其中的一个点
int find_circle(int x)
{
	bool v[MaxN];
	memset(v,0,sizeof(v));
	int t = in[x];
	v[x] = true;
	while (t&&!v[in[t]])
		v[t] = true, t = in[t];
	return t;
}

int min_tree_pic()
{
	int i,j,k,u,tt,t,ans = 0;
	memset(used,false,sizeof(used));
	count = 0; dfs(0);
	if (count<n+1) return -1;
	memset(used,false,sizeof(used));
	//初始in数组
	for (i=1,k=0,in[0]=-1; i<=n; i++) {
		for (j=0,t=oo; j<=n; j++)
			if (!used[j]&&d[j][i]&&t>a[j][i]) {
				t = a[j][i]; k = j;
			}
		in[i] = k; mindis[i] = t;
	}
	while (true) {
		for (i=1; i<=n; i++)
		 if (!used[i]&&(tt=find_circle(i))) {
			i = tt;
			u = in[i];
			ans += mindis[i];
			while (u-i) {
				used[u] = true;
				ans += mindis[u]; u = in[u];
			}
			for (j=0; j<=n; j++)
			 if (!used[j]&&j-i)
				a[j][i] -= mindis[i];
			for (j=0; j<=n; j++)
			 if (!used[j]&&j-i) {
				for (u=in[i]; u-i; u=in[u]) {
					if(d[u][j]&&(a[u][j]<a[i][j]||!d[i][j]))   //更新dis[i][j]
						a[i][j]=a[u][j],d[i][j]=true;
					if(d[j][u]&&(a[j][u]-mindis[u]<a[j][i]||!d[j][i]))//更新dis[j][i]
						a[j][i]=a[j][u]-mindis[u],d[j][i]=true;				
				}
			 }
			break;
		 }
		if (i>n) break;
		for(i=1,in[0]=-1;i<=n;i++)if(!used[i])  //需要重新生成in
		{
			for(j=0,t=oo,k=0;j<=n;j++)if(!used[j]&&d[j][i]&&t>a[j][i])
			t=a[j][i],k=j;
			in[i]=k;mindis[i]=t;
		}
	}
	for(i=1;i<=n;i++)if(!used[i])   //加上最后不成环的结点的mindis值
		ans+=mindis[i]; 
	return ans;
}

int main()
{
	freopen("salenet.in","r",stdin);
	freopen("salenet.out","w",stdout);
	
	int p,r,x,y,z;
	
	scanf("%d",&n);

	memset(d,false,sizeof(d));
	memset(a,0,sizeof(a));
	scanf("%d",&p);
	for (int i=1; i<=p; i++) {
		scanf("%d%d",&y,&z);
		a[0][y] = z;
		d[0][y] = true;
	}
	scanf("%d",&r);
	for (int i=1; i<=r; i++) {
		scanf("%d%d",&x,&y);
		a[x][y] = 0; d[x][y] = true;
	}
	for (int i=0; i<=n; i++)
		d[i][i] = 0;
	
	int ans = min_tree_pic();
	if (ans<0) {
		printf("NO\n");
		for (int i=1; i<=n; i++)
			if (!used[i]) { printf("%d\n",i); break;}
	}
	else printf("YES\n%d\n",ans);
	
	fclose(stdin); fclose(stdout);
	return 0;
}