http://acm.nyist.net/JudgeOnline/problem.php?pid=118&&차 소 생 성 트 리
2087 단어 c
코드:
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 501
#define M 9999999
#define MM -999999
using namespace std;
int map[N][N],maxs[N][N],dist[N];
bool visit[N];
int n,m;
bool prim()
{ int pre[N]={0};
int now=1;
dist[now]=0;
visit[now]=false;
for(int i=2;i<=n;++i)
{ visit[i]=true;
dist[i]=map[now][i];
pre[i]=now;
}
for(int i=1;i<n;++i)
{ int minx=M;
for(int j=1;j<=n;++j)
if(visit[j]&&dist[j]<minx)
minx=dist[now=j];
visit[now]=false;
int pr=pre[now];
maxs[pr][now]=maxs[now][pr]=map[pr][now];
for(int j=1;j<=n;++j) ,,,
if(!visit[j])
maxs[j][now]=max(maxs[j][pr],maxs[now][pr]);
for(int j=1;j<=n;++j)
if(visit[j]&&dist[j]>map[now][j])
dist[j]=map[now][j],pre[j]=now;
}
for(int j=1;j<=n;++j)
for(int i=1;i<=n;++i)
{
if(pre[i]==j||pre[j]==i) continue;
else if(maxs[j][i]==map[i][j]) return true; , ,,,
}
return false;
}
int main()
{ int Case;
cin>>Case;
while(Case--)
{ cin>>n>>m;
for(int j=1;j<=n;++j)
for(int i=1;i<=n;++i)
{map[i][j]=M;
maxs[i][j]=MM;
}
for(int i=1;i<=m;++i)
{ int a,b,c;
cin>>a>>b>>c;
if(map[a][b]>c)
map[a][b]=map[b][a]=c;
}
if(prim()) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
} return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Docker를 사용한 React 및 .NET Core 6.0 샘플 프로젝트 - 1부이 기사에서는 Entity Framework Core Code First 접근 방식을 사용하는 ASP.NET Core 6.0 WEP API의 CRUD(만들기, 읽기, 업데이트 및 삭제) 작업에 대해 설명합니다. 웹 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.