zoj 2326 Tangled in Cables【kruskal】
Tangled in Cables
Time Limit: 1 Second
Memory Limit: 32768 KB
You are the owner of SmallCableCo and have purchased the franchise rights for a small town. Unfortunately, you lack enough funds to start your business properly and are relying on parts you have found in an old warehouse you bought. Among your finds is a single spool of cable and a lot of connectors. You want to figure out whether you have enough cable to connect every house in town. You have a map of town with the distances for all the paths you may use to run your cable between the houses. You want to calculate the shortest length of cable you must have to connect all of the houses together.
Input
Only one town will be given in an input.
Output
The output will consist of a single line. If there is not enough cable to connect all of the houses in the town, output
Not enough cable
If there is enough cable, then output
Need
Print X to the nearest tenth of a mile (0.1).
Sample Input
100.0 4 Jones Smiths Howards Wangs 5 Jones Smiths 2.0 Jones Howards 4.2 Jones Wangs 6.7 Howards Wangs 4.0 Smiths Wangs 10.0
Sample Output
Need 10.2 miles of cable
//2606646 2011-07-30 15:39:28 Accepted 2326 C++ 0 12144 ylwh!
//2606639 2011-07-30 15:37:44 Segmentation Fault 2326 C++ 0 0 ylwh!
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#define N 10000
#define M 1000000 //
#include <algorithm>
using namespace std;
int n, m, ncount, pre[N];
char name[N][21];
float sum_len, min_len;
struct edge
{
int x, y;
float len;
}node[M];
bool cmp(struct edge a, struct edge b)
{
return a.len < b.len;
}
int search_name(char * s)
{
int i;
for(i=1; i<=n; i++)
if( !strcmp(s, name[i]) )
return i;
}
void input()
{
int i, x, y;
char s[21];
scanf("%d", &n);
for(i=1; i<=n; i++)
scanf("%s", name[i]);
scanf("%d", &m);
for(i=1; i<=m; i++)
{
scanf("%s", s);
x = search_name(s);
scanf("%s", s);
y = search_name(s);
ncount++;
node[ ncount ].x = x;
node[ ncount ].y = y;
scanf("%f", &node[ ncount ].len);
}
}
int find_pre(int x)
{
while( x != pre[x] )
x = pre[x];
return x;
}
void kruskal()
{
int i, j, a, b;
for(i=1; i<=n; i++)
pre[i] = i;
sort(node+1, node+m+1, cmp);
for(i=1; i<=m; i++)
{
a = find_pre( node[i].x );
b = find_pre( node[i].y );
if( a != b )
{
min_len += node[i].len;
pre[ b ] = a;
}
}
if(sum_len < min_len)
printf("Not enough cable
");
else
printf("Need %.1f miles of cable
", min_len);
}
int main()
{
int i;
while( scanf("%f", &sum_len) != EOF )
{
ncount = 0;
min_len = 0;
input();
kruskal();
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Ruby의 구조체 클래스은 접근자 메서드가 있는 속성 모음입니다. 클래스를 명시적으로 작성할 필요 없이. Struct 클래스는 구성원 및 해당 값 집합을 포함하는 새 하위 클래스를 생성합니다. 각 멤버에 대해 #attr_accessor 와...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
