nyoj--118--修路方案（次小生成树）

修路方案

时间限制：3000 ms | 内存限制：65535 KB

难度：5

描述

南将军率领着许多部队，它们分别驻扎在N个不同的城市里，这些城市分别编号1~N，由于交通不太便利，南将军准备修路。

现在已经知道哪些城市之间可以修路，如果修路，花费是多少。

现在，军师小工已经找到了一种修路的方案，能够使各个城市都联通起来，而且花费最少。

但是，南将军说，这个修路方案所拼成的图案很不吉利，想让小工计算一下是否存在另外一种方案花费和刚才的方案一样，现在你来帮小工写一个程序算一下吧。

输入

第一行输入一个整数T(1<T<20)，表示测试数据的组数

每组测试数据的第一行是两个整数V,E，(3<V<500,10<E<200000)分别表示城市的个数和城市之间路的条数。数据保证所有的城市都有路相连。

随后的E行，每行有三个数字A B L，表示A号城市与B号城市之间修路花费为L。

输出

对于每组测试数据输出Yes或No（如果存在两种以上的最小花费方案则输出Yes,如果最小花费的方案只有一种，则输出No)

样例输入

样例输出

No

Yes

来源

POJ题目改编

上传者

张云聪

次小生成树，这道题我用的克鲁斯卡尔实现，先找到最小生成树，然后开始枚举，每次排除一条边，看是否能找到下一个最小生成树，找到的时候一定要判断是不是已经把每一条边全部连入！！

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

struct node

{

	int u,v,val;

	int flog;

}edge[200000+10];

int pre[1000],m,n,minn;

void init()

{

	for(int i=0;i<1000;i++)

	pre[i]=i;

}

int cmp(node s1,node s2)

{

	return s1.val<s2.val;

}

int find(int x)

{

	return pre[x]==x?x:pre[x]=find(pre[x]);

}

int F(int w)

{

	int sum=0;

	for(int i=0;i<m;i++)

	{

		if(i!=w)

		{

			int fx=find(edge[i].u);

			int fy=find(edge[i].v);

			if(fx!=fy)

			{

				pre[fx]=fy;

				sum+=edge[i].val;

			}

		}

	}

	int s=find(1);//判断全部的点是不是已经全部连进去

	for(int i=2;i<=n;i++)

	if(pre[i]!=s)

	return -1;

	return sum;

}

int main()

{

	int t;

	scanf("%d",&t);

	while(t--)

	{

		init();

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

		for(int i=0;i<m;i++)

		scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].val),edge[i].flog=0;

		sort(edge,edge+m,cmp);

		minn=0;

		for(int i=0;i<m;i++)//找到最小生成树

		{

			int fx=find(edge[i].u);

			int fy=find(edge[i].v);

			if(fx!=fy)

			{

				pre[fx]=fy;

				edge[i].flog=1;//标记这条边在最小生成树中已经用过

				minn+=edge[i].val;

			}

		}

		int flag=0;

		for(int i=0;i<m;i++)

		{

			if(edge[i].flog)//每次排除一条边

			{

				init();

				if(F(i)==minn)

				{

					flag=1;

					break;

				}

			}

			if(flag) break;

		}

		if(flag) printf("Yes\n");

		else printf("No\n");

	}

	return 0;

}

巴特西

nyoj--118--修路方案（次小生成树）

修路方案

最新文章

热门文章