NYOJ 118は次の小さい生成の木を求めます
2842 ワード
中国語の問題.
アルゴリズムの構想:次の小さい生成木を求めます.
アルゴリズムの構想:次の小さい生成木を求めます.
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXN 505
int t,n,m,a,b,c,sum,e,MAX,pr;
int maps[MAXN][MAXN],dist[MAXN],p[MAXN][MAXN],pre[MAXN];
bool visited[MAXN],used[MAXN][MAXN];
void prim(int s)
{
int MIN,node;
memset(visited,false,sizeof(visited));
memset(used,false,sizeof(used));
memset(p,0,sizeof(p));
memset(dist,0x3f,sizeof(dist));
memset(pre,0,sizeof(pre));
for(int i=1; i<=n; i++)
{
used[i][i]=true;
//dist[i]=maps[1][i];
// pre[i]=1;
}
dist[1]=0;
for(int i=1; i<=n; i++)
{
MIN=INF,node=-1;
for(int j=1; j<=n; j++)
{
if(!visited[j]&&MIN>dist[j])
{
MIN=dist[j];
node=j;
}
}
if(node==-1)
return;
visited[node]=true;
sum+=dist[node];
pr=pre[node];
p[pr][node]=p[node][pr]=dist[node];
maps[pr][node]=maps[node][pr]=0;
for(int j=1;j<=n;j++)
{
if(visited[j]&&j!=node)
p[j][node]=p[node][j]=max(p[j][pr],dist[node]);
}
for(int j=1; j<=n; j++)
{
if(!visited[j]&&maps[node][j]&&dist[j]>maps[node][j])
{
pre[j]=node;
dist[j]=maps[node][j];
}
}
}
}
int main()
{
scanf("%d",&t);
while(t--)
{
memset(maps,0,sizeof(maps));
MAX=-INF;
sum=0;
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++)
{
scanf("%d%d%d",&a,&b,&c);
maps[a][b]=maps[b][a]=c;
}
prim(1);
int res=INF;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(maps[i][j])
{
res=min(res,sum+maps[i][j]-p[i][j]);
}
}
}
if(res==sum)
printf("Yes
");
else
printf("No
");
}
return 0;
}