hdu 1879 계속 원활 한 프로젝트(최소 생 성 트 리)
5523 단어 최소 생 성 트 리
/************************************************************************/
/*
hdu
:
: , , 0,
,
*/
/************************************************************************/
#include <stdio.h>
#include <string.h>
#include <algorithm>
const int N = 101;
int map[N][N];
int mark[N];
int i,j,n;
int prim()
{
int sum = 0;
int min,t = n,k;
while(--t)
{
min = 100000;
for (i = 2; i <= n; i++)
{
if(mark[i] != 1 && min > map[1][i])
{
min = map[1][i];
k = i;
}
}
sum += min;
mark[k] = 1;
for (i = 2; i <= n; i++)
{
if(mark[i] != 1 && map[k][i] < map[1][i])
map[1][i] = map[k][i];
}
}
return sum;
}
int main()
{
int x,y,fee,flag,num;
while(scanf("%d",&n) && n != 0)
{
num = n*(n-1)/2;
memset(map,0,sizeof(map));
for (i = 1; i <= num; i++)
{
scanf("%d%d%d%d",&x,&y,&fee,&flag);
if(flag == 1)map[x][y] = map[y][x] = 0;
else map[x][y] = map[y][x] = fee;
}
memset(mark,0,sizeof(mark));
printf("%d
",prim());
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU 1875 는 최소 생 성 트 리 입 니 다.그들 이 다른 작은 섬 에 가 고 싶 을 때 작은 배 를 저어 이 루어 져 야 합 니 다.현재 정 부 는 백도 호 를 대대적으로 발전 시 키 기로 결정 했다. 조건 에 맞 는 다 는 것 은 작은 섬 2 곳 사이 의 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.