poj3522——Slim Span
1579 단어 도 론
분석: 최소 생 성 트 리.원제 = > 작은 것 부터 큰 것 까지 정렬 한 후 앞의 m - n + 1 개의 변 을 Krustal 로 하여 최소 생 성 트 리 의 최소 변 을 구하 십시오.krustal 알고리즘 은 n - 1 개의 변 을 찾 아야 하기 때문에 앞의 m - (n - 1) 개 만 이 매번 krustal 의 최소 변 으로 사용 할 수 있 습 니 다.
코드:
#include
#include
using namespace std;
struct Edge{
int a,b,w;
} edge[5000];
int fa[110];
bool cmp(const Edge& a,const Edge& b) {
return a.w < b.w;
}
int find(int x) {
if(x != fa[x]) return fa[x] = find(fa[x]);
return fa[x];
}
int main() {
int n,m;
while(cin >> n >> m) {
if (n + m == 0) break;
for(int i = 0;i < m;i++)
cin >> edge[i].a >> edge[i].b >> edge[i].w;
sort(edge,edge + m,cmp);
int slimness = 0x3f3f3f3f;
for(int i = 0;i <= m - n + 1;i++) {
for(int j = 0;j <= n;j++)
fa[j] = j;
int k = 0;
for(int j = i;j < m;j++) {
int x1 = find(edge[j].a),x2 = find(edge[j].b);
if(x1 != x2) {
k++;
fa[x1] = x2;
}
if(k == n - 1) {
slimness = min(slimness,edge[j].w - edge[i].w);
break;
}
}
}
if (slimness == 0x3f3f3f3f) cout << -1 << endl;
else cout << slimness << endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU 1874: 원활 한 공사 계속 [Dijkstra & SPFA & Floyd]모 성 은 여러 해 동안 의 원활 한 공사 계획 을 실행 한 후에 마침내 많은 길 을 건설 하 였 다.길 을 많이 건 너 지 않 아 도 좋 지 않다. 한 도시 에서 다른 도시 로 갈 때마다 여러 가지 도로 방안 을 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
