修路方案
3000 ms | 内存限制： 65535
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)
样例输入
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
//这个代码一直WA，但我一直找不出来
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MIN(a,b) a>b?b:a
#define INF 0x3f3f3f3f
#define MAX(a,b) a>b?a:b
using namespace std;
int n,m;
int dis[600],vis[600],map[600][600];
void prim(int x)
{
memset(vis,0,sizeof(vis));
int i,j,k,min,sum=0,cnt;
for(i=1;i<=n;i++)
{
dis[i]=map[1][i];
}
dis[x]=0;
vis[x]=1;
for(j=1;j<n;j++)
{
k=1;min=INF;cnt=0;
for(i=1;i<=n;i++)
{
if(!vis[i]&&dis[i]<min)
{
min=dis[i];
k=i;
}
}
for(i=1;i<=n;i++)
{
if(vis[i]&&map[k][i]==min)
cnt++;
}
if(cnt>2)
{
printf("Yes\n");
return ;
}
sum+=min;
vis[k]=1;
for(i=1;i<=n;i++)
{
if(!vis[i]&&dis[i]>=map[k][i])
dis[i]=map[k][i];
}
}
printf("No\n");
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int i,j;
int a,b,c;
scanf("%d%d",&n,&m);
memset(map,INF,sizeof(map));
while(m--)
{
scanf("%d%d%d",&a,&b,&c);
if(map[a][b]>c)
map[a][b]=map[b][a]=c;
}
prim(1);
}
return 0;
}
//参考别人的代码，要用到次小生成树（还没看到过）
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define maxN 510
#define MAX 0x0fffffff
#define MIN -0x0fffffff
int N,M,map[maxN][maxN],dis[maxN],maxlen[maxN][maxN],pre[maxN];
bool vis[maxN];
int prim()
{
int i,j,k,minn,pr;
memset(vis,false,sizeof(vis));
for(i=1; i<=N; i++)
{
dis[i]=map[1][i];
pre[i]=1;
}
vis[1]=true;
for(j=1; j<N; j++)
{
minn = MAX;
for(i=1; i <= N; i++)
{
if(!vis[i] && dis[i]<minn)
{
minn=dis[k=i];
}
}
pr = pre[k];
maxlen[k][pr] = maxlen[pr][k] = map[k][pr];
for(i = 1; i <= N; i++)
if(vis[i])
maxlen[i][k]=maxlen[k][i]=max(maxlen[i][pr],maxlen[pr][k]);
vis[k]=true;
for(i=1; i<=N; i++)
{
if(!vis[i]&&dis[i]>map[k][i])
{
dis[i]=map[i][k];
pre[i]=k;
}
}
}
for(i=1; i < N; i++)
{
for(j = i+1; j <= N; j++)
{
if(pre[i] == j|| pre[j] == i)
continue;
else if(maxlen[i][j] == map[i][j])
return 1;
}
}
return 0;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int u,v,w;
scanf("%d%d",&N,&M);
for(int i = 0; i <= N; i++)
{
for(int j=0; j <= N; j++)
{
map[i][j] = MAX;
maxlen[i][j] = MIN;
}
}
for(int i = 0; i < M; i++)
{
scanf("%d%d%d",&u,&v,&w);
map[u][v]=map[v][u]=w;
}
if(prim())
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
//看到大神的对次小生成树的讲解，感觉很好，贴上代码，及思路。。。
算法核心思想：在prime求MST的过程中 用数组存储MST里面任意两点间的唯一的路中 权值最大的那条边的权值。最后枚举不在MST里面的边<i,，j>，判断<i，j>的权值 是否 和 MST里面 i 到 j 的最大权值相等，只要有一条边满足就可以说明MST不唯一。（因为我们可以用这条不在MST的边来 代替 在MST的边，这样MST肯定不唯一）
数组使用
prime 模版用到三个数组 low[] vis[] Map[][]，不再详细解释。
MST[ i ][ j ] : 存储MST中i 到 j 的唯一的路中 权值最大的那条边的权值。
InMST[ i ][ j ] : 判断<i，j>这条边是否在MST中.
pre[ i ] : 记录 i 点的前驱 fa ，low[ i ] = Map[ fa ][ i ]。
对于选入MST的点next
MST更新：MST[ next ][ j ] = max(MST[ pre[ next ] ][ j ], low[ next ])。（ j 属于MST里面的点）
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 500+10
#define INF 100000000
using namespace std;
int Map[MAXN][MAXN];
bool vis[MAXN];
int low[MAXN];//上面三个数组 求MST 专用
int MST[MAXN][MAXN];//MST中 i 和 j的最大边权
int pre[MAXN];//记录前驱
bool InMST[MAXN][MAXN];//标记该边是否在MST中
int N, M;
void init()
{
for(int i = 1; i <= N; i++)
{
Map[i][i] = 0;
for(int j = 1; j < i; j++)
Map[i][j] = Map[j][i] = INF;
}
}
void getMap()
{
int a, b, c;
for(int i = 1; i <= M; i++)
{
scanf("%d%d%d", &a, &b, &c);
if(Map[a][b] > c)
Map[a][b] = Map[b][a] = c;
}
}
void solve()
{
//prime求MST
int mincost = 0;//最小代价
int next, Min;
memset(InMST, false, sizeof(InMST));
memset(MST, 0, sizeof(MST));
for(int i = 1; i <= N; i++)
{
low[i] = Map[1][i];
vis[i] = false;
pre[i] = 1;//每个点前驱
}
vis[1] = true;
for(int i = 2; i <= N; i++)
{
Min = INF; next = -1;
for(int j = 1; j <= N; j++)
{
if(!vis[j] && Min > low[j])
{
next = j;
Min = low[j];
}
}
mincost += Min;
vis[next] = true;
int fa = pre[next];//当前找到点的 前驱
InMST[next][fa] = InMST[fa][next] = true;//在MST中
for(int j = 1; j <= N; j++)
{
if(vis[j] && j != next)//MST中的点
MST[j][next] = MST[next][j] = max(MST[fa][j], low[next]);
if(!vis[j] && low[j] > Map[next][j])//更新low
{
low[j] = Map[next][j];
pre[j] = next;//更新前驱
}
}
}
//判断MST是否唯一
for(int i = 1; i <= N; i++)
{
for(int j = 1; j < i; j++)
{
if(Map[i][j] != INF && !InMST[i][j])//有边 且不在MST中
{
if(Map[i][j] == MST[i][j])
{
printf("Yes\n");
return ;
}
}
}
}
printf("No\n");
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d", &N, &M);
{
init();
getMap();
solve();
}
}
return 0;
}