- 描述
南将军率领着许多部队，它们分别驻扎在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)
- 样例输入
2
3 3
1 2 1
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2- 样例输出
No
Yes- 来源
- POJ题目改编
- 上传者
- 张云聪
题意:次小生成树
WA代码:
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <queue>
using namespace std; #define MAX 200020
#define INF 0x3f3f3f3f struct edge
{
int x,y,cost;
int flag;
}; edge e[MAX];
int f[MAX];
int dis[MAX];
int v,n,m,ans; bool cmp(edge a,edge b)
{
return a.cost<b.cost;
} void init(int n)
{
for(int i=;i<=n;i++)
f[i]=i;
} int find(int x)
{
if(x!=f[x])
f[x]=find(f[x]);
return f[x];
} void Union(int x,int y)
{
x=find(x);
y=find(y);
f[y]=x;
} int same(int x,int y)
{
return find(x)==find(y);
} int kruskal_1(int n,int m)
{
int ans=;
for(int i=;i<m;i++)
{
if(!same(e[i].x,e[i].y))
{
e[i].flag=;
Union(e[i].x,e[i].y);
ans+=e[i].cost;
}
}
return ans;
} int kruskal_2(int n,int m)
{
int ans=,cnt=;
for(int i=;i<m;i++)
{
if (i == n)//除去这条边之后再求一次最小生成树
continue;
if(!same(e[i].x,e[i].y))
{
Union(e[i].x,e[i].y);
ans+=e[i].cost;
cnt++;
}
}
if(cnt!=n)
return -;
else
return ans;
} int main()
{
int t;
scanf("%d",&t);
while(t--){
init(n);
memset(e,,sizeof(e));
int v=;
scanf("%d%d",&n,&m);
int count;
for(int i=; i<m; i++){
scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].cost);
e[i].flag=;
}
sort(e,e+m,cmp);
int flag=,prim_2;
int prim_1=; prim_1=kruskal_1(n,m);
/*for(int i=0; i<m; i++){
cout<<e[i].x<<e[i].y<<e[i].cost<<e[i].flag<<endl;
}*/ for(int i=; i<m; i++){
if(e[i].flag==)
continue;
prim_2=;
init(n);
prim_2=kruskal_2(i,m);
if(prim_2==prim_1){
flag=;
break;
}
} if(prim_1==prim_2){
flag=;
} if(flag)
printf("Yes\n");
else
printf("No\n");
}
}
AC代码:
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{
int u,v,val;
int flog;
}edge[+];
int pre[],m,n,minn;
void init()
{
for(int i=;i<;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=;
for(int i=;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();//判断全部的点是不是已经全部连进去
for(int i=;i<=n;i++)
if(pre[i]!=s)
return -;
return sum;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
init();
scanf("%d%d",&n,&m);
for(int i=;i<m;i++)
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].val),edge[i].flog=;
sort(edge,edge+m,cmp);
minn=;
for(int i=;i<m;i++)//找到最小生成树
{
int fx=find(edge[i].u);
int fy=find(edge[i].v);
if(fx!=fy)
{
pre[fx]=fy;
edge[i].flog=;//标记这条边在最小生成树中已经用过
minn+=edge[i].val;
}
}
int flag=;
for(int i=;i<m;i++)
{
if(edge[i].flog)//每次排除一条边
{
init();
if(F(i)==minn)
{
flag=;
break;
}
}
if(flag) break;
}
if(flag) printf("Yes\n");
else printf("No\n");
}
return ;
}