Test 6.29 T3 小学生

问题描述

“不错,不错!那么,准备好迎接下一道题了么?”一道白光闪过,CJK 眼前出现了 1e100 个小学生。“他们中,有一些人轨了我的机子。现在,我需要你在 1S 之内找出他们,并让他们认错!”凭借自己无所不知的神(xuan)奇(xue)力量, CJK 立刻发现了轨了 JesseLiun的机子的那 n 个小学生。但是,他还要想办法让小学生们认错。好在 CJK 有无穷多的糖,而有 p 个小学生愿意以一定的代价被收买。而小学生间有 r 个 BiShi 关系。一旦一个小学生被收买,他就会主动认错,并告发他 BiShi 的人,逼迫他们认错。那些被逼认错的人,也会告发他 BiShi 的人,以此类推。

输入格式

第一行两个数,n 和 p。紧接着 p 行,一行两个数 x 和 y,表示编号为 x 的小学生愿意以 y 的代价被收买。接下来一行是 m,紧跟着 m 行,每一行两个数字 x和 y,表示编号为 x 的小学生 BiShi 编号为 y 的小学生(当然,这并不意味着编号为 y 的会 BiShi 编号为 x 的)。

输出格式

如果 CJK 能让所有 n 个小学生认错,输出“YES”,并在下一行输出所需花费的最少糖果数。如果不能,输出“NO”,并在下一行输出编号最小的、且不会认错的小学生。

样例输入输出

样例输入1

3

2

1 10

2 100

2

1 3

2 3

样例输出1

YES

110

样例输入2

4

2

1 100

4 200

2

1 2

3 4

样例输出2

NO

3

解析

正解是Tarjan缩环，新点的权值为环上最小值，然后再DAG动态规划。一个点如果能被其他点达到的话，就没有必要选择这个点。

由于考场上忘了Tarjan，临时想出来一个做法，差不多就是先每个点跑一边DFS统计一个点可以由哪些点达到，然后和上面一样的逻辑，如果两个关键点可以互达说明有环，这时取最小值。否则则为能到达对方的点。

代码

#include <iostream>

#include <cstdio>

#include <cstring>

#define N 3002

#define M 20002

using namespace std;

int head[N],ver[M],nxt[M],l;

int m,n,p,w[N],i,j,f[N],g[N],a[N];

bool vis[N],e[N][N],key[N];

void insert(int x,int y)

{

	l++;

	ver[l]=y;

	nxt[l]=head[x];

	head[x]=l;

}

int min(int x,int y)

{

	if(w[x]<w[y]) return x;

	return y;

}

void dfs(int x,int node)

{

	vis[x]=1;

	for(int i=head[x];i;i=nxt[i]){

		int y=ver[i];

		if(!vis[y]){

			e[node][y]=1;

			dfs(y,node);

		}

	}

}

void dp(int x,int kid)

{

	if(vis[x]) return;

	vis[x]=1;

	if(f[x]==0) f[x]=kid;

	else if(e[kid][f[x]]&&!e[f[x]][kid]) f[x]=kid;

	else if(e[kid][f[x]]&&e[f[x]][kid]) f[x]=min(f[x],kid);

	for(int i=head[x];i;i=nxt[i]){

		int y=ver[i];

		if(f[y]!=kid) dp(y,kid);

	}

}

int main()

{

	freopen("pupil.in","r",stdin);

	freopen("pupil.out","w",stdout);

	cin>>n>>p;

	for(i=1;i<=p;i++){

		int x;

		cin>>a[i]>>x;

		w[a[i]]=x;

	}

	cin>>m;

	for(i=1;i<=m;i++){

		int u,v;

		cin>>u>>v;

		insert(u,v);

	}

	for(i=1;i<=n;i++) e[i][i]=1;

	for(i=1;i<=p;i++){

		memset(vis,0,sizeof(vis));

		dfs(a[i],a[i]);

	}

	for(i=1;i<=p;i++){

		memset(vis,0,sizeof(vis));

		dp(a[i],a[i]);

	}

	int ans=0;

	memset(vis,0,sizeof(vis));

	for(i=1;i<=n;i++){

		if(f[i]==0){

			cout<<"NO"<<endl<<i<<endl;

			return 0;

		}

		else if(!vis[f[i]]) ans+=w[f[i]],vis[f[i]]=1;

	}

	cout<<"YES"<<endl<<ans<<endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}

跑的贼慢......

巴特西