BZOJ 1050 [HAOI 2006] travel comf (Kruskal 알고리즘)
1939 단어 최소 생 성 트 리bzoj
m ^ 2 의 알고리즘 을 설계 할 수 있 습 니 다:
먼저 변 을 길이 에 따라 정렬 한 다음 에 매번 최소 변 의 길이 w [i] 를 한정 하여 더 큰 변 을 추가 합 니 다.
어느 쪽 w [j] 에 추가 하면 s 와 t 가 연결 되 고 (집합 판단) w [j] / w [i] (double 형식) 로 답 을 업데이트 합 니 다.
s 와 t 를 연결 할 수 있 는 w [i] 가 없 으 면 풀 리 지 않 습 니 다.
주의: 경로 에서 나 누 어 진 '곁가지' 는 상관 하지 않 아 도 됩 니 다. 왜냐하면 그들의 길 이 는 최소 도 아니 고 최대 도 아니 기 때 문 입 니 다. 제거 한 후에 s, t 는 계속 연결 되 어 답 에 영향 을 주지 않 습 니 다.
#include<stdio.h>
#include<stdlib.h>
int fa[10005]={0},u[10005]={0},v[10005]={0},w[10005]={0};
int father(int x)
{
if(fa[x]!=x) fa[x]=father(fa[x]);
return fa[x];
}
void jh(int* a,int* b)
{
int t=*a;
*a=*b;
*b=t;
}
void kp(int low,int high)
{
int i=low,j=high,mid=w[(i+j)/2];
while(i<j)
{
while(w[i]<mid) i++;
while(w[j]>mid) j--;
if(i<=j)
{
jh(&u[i],&u[j]);
jh(&v[i],&v[j]);
jh(&w[i],&w[j]);
i++;
j--;
}
}
if(j>low) kp(low,j);
if(i<high) kp(i,high);
}
int gcd(int a,int b)
{
if(b==0) return a;
return gcd(b,a%b);
}
int main()
{
int n,m,i,j,s,t,min=-1,max=-1;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
scanf("%d%d%d",&u[i],&v[i],&w[i]);
scanf("%d%d",&s,&t);
kp(1,m);
for(i=1;i<=m;i++)// :w[i]
{
if(w[i]==w[i-1]) continue;//
for(j=1;j<=n;j++)
fa[j]=j;
for(j=i;j<=m;j++)
{
if(father(u[j])!=father(v[j])) fa[father(u[j])]=father(v[j]);
if(father(s)==father(t)) break;
}
if(j<=m&&(min==-1||(double)max/(double)min>(double)w[j]/(double)w[i]))
{
min=w[i];
max=w[j];
}
}
if(min==-1) printf("IMPOSSIBLE");
else
{
if(max%min==0) printf("%d",max/min);
else printf("%d/%d",max/gcd(max,min),min/gcd(max,min));
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU 1875 는 최소 생 성 트 리 입 니 다.그들 이 다른 작은 섬 에 가 고 싶 을 때 작은 배 를 저어 이 루어 져 야 합 니 다.현재 정 부 는 백도 호 를 대대적으로 발전 시 키 기로 결정 했다. 조건 에 맞 는 다 는 것 은 작은 섬 2 곳 사이 의 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
