题解 UVA10859 【Placing Lampposts】

交了N次，重构一次代码终于过了.....

题意：一片森林，1.输出占领所有边需要的最小的路灯个数 2.输出两端点均被占领的边的条数 3.只有一端被占领的边的条数

还是比较简单的

开始的时候思路不够清晰，写的时候很多东西都没注意到

导致一直WA，重构的时候好多了，一遍过

开两个DP数组，一个存路灯个数，一个存两端都被占领的边的个数

感觉更好理解一些

以下是代码

#include<cstdio>

#include<cstring>

#define N 100005

int n,m,cnt,T,ans1,ans2,a,b;

int head[N],vis[N];

int dp[N][2],f[N][2];

struct node{

	int v,nex;

}e[N];

void dfs(int u,int fa){

	dp[u][1]=1;

	vis[u]=1;

	for(int i=head[u];i;i=e[i].nex){

		int v=e[i].v;

		if(vis[v]) continue;

		dfs(v,u);

		dp[u][0]+=dp[v][1];

		f[u][0]+=f[v][1];

		if(dp[v][1]<dp[v][0]){

			dp[u][1]+=dp[v][1];

			f[u][1]+=f[v][1]+1;

		}

		else if(dp[v][1]>dp[v][0]){

			dp[u][1]+=dp[v][0];

			f[u][1]+=f[v][0];

		}

		else{					//这里进行一步特判，满足第二个条件

			dp[u][1]+=dp[v][0];

			if(f[v][1]+1>f[v][0]){

				f[u][1]+=f[v][1]+1;

			}

			else{

				f[u][1]+=f[v][0];

			}

		}

	}

}

void add(int u,int v){

	cnt++;

	e[cnt].v=v;

	e[cnt].nex=head[u];

	head[u]=cnt;

}

void init(){

	cnt=ans1=ans2=0;

	memset(head,0,sizeof head);

	memset(vis,0,sizeof vis);

	memset(dp,0,sizeof dp);

	memset(f,0,sizeof f);

}

int main(){

	scanf("%d",&T);

	while(T--){

		init();

		scanf("%d%d",&n,&m);

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

			scanf("%d%d",&a,&b);

			a++,b++;

			add(a,b);add(b,a);

		}

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

			if(!vis[i]){		//可能是森林，注意！！

				dfs(i,0);

				if(dp[i][0]>dp[i][1]){

					ans1+=dp[i][1];

					ans2+=f[i][1];

				}

				else if(dp[i][0]<dp[i][1]){

					ans1+=dp[i][0];

					ans2+=f[i][0];

				}

				else{			//同上

					ans1+=dp[i][0];

					if(f[i][1]>f[i][0]){

						ans2+=f[i][1];

					}

					else{

						ans2+=f[i][0];

					}

				}

			}

		}

		printf("%d %d %d\n",ans1,ans2,m-ans2);

	}

	return 0;

}

巴特西

题解 UVA10859 【Placing Lampposts】

最新文章

热门文章