【会津】パソコン甲子園2004【若松】

[1 デフォルトの名無しさん NG NG]

今日プログラミング部門の予選が行われましたが
手応えはどうでしたか？

http://www.pref.fukushima.jp/pc-concours/

[187 デフォルトの名無しさん NG NG]

遅くなりますた。
050の問題は最小全域木問題だよ。
Kruskal のアルゴリズムを使うとこんな感じ。

[188 デフォルトの名無しさん NG NG]

#include <stdio.h>
#include <stdlib.h>

#define MAX_SITE 1000
#define MAX_EDGE (MAX_SITE*(MAX_SITE-1)/2)

struct edge {
　int from;
　int to;
　int length;
};

struct edge Path[MAX_EDGE];
int N_path;

int SiteSet[MAX_SITE];
int N_site;

int cmp_int(struct edge *x, struct edge *y)
{
　return x->length - y->length;
}

[189 デフォルトの名無しさん NG NG]

int
main()
{
　int i,j,f_no,t_no;
　int pathlen = 0;
　FILE *f;

　f = fopen("050.csv","r");
　fscanf(f,"%d",&N_site);
　i = 0;
　while (fscanf(f,"%d,%d,%d",&Path[i].from,&Path[i].to,&Path[i].length) == 3)
　　i++;
　N_path = i;
　fclose(f);

[190 デフォルトの名無しさん NG NG]

i　qsort(Path,N_path,sizeof(struct edge),cmp_int);
　for (i = 0; i < N_site; i++)
　　SiteSet[i] = i;
　for (i = 0; i < N_path; i++) {
　　if (SiteSet[Path[i].from] != SiteSet[Path[i].to]) {
　　　f_no = SiteSet[Path[i].from];
　　　t_no = SiteSet[Path[i].to];
　　　for (j = 0; j < N_site; j++) {
　　　　if (SiteSet[j] == t_no)
　　　　　SiteSet[j] = f_no;
　　　}
　　　pathlen += Path[i].length;
　　}
　}
　printf("%d\n",pathlen/100);
　　return 0;
}

[191 デフォルトの名無しさん NG NG]

　qsort(Path,N_path,sizeof(struct edge),cmp_int);
　for (i = 0; i < N_site; i++)
　　SiteSet[i] = i;
　for (i = 0; i < N_path; i++) {
　　if (SiteSet[Path[i].from] != SiteSet[Path[i].to]) {
　　　f_no = SiteSet[Path[i].from];
　　　t_no = SiteSet[Path[i].to];
　　　for (j = 0; j < N_site; j++) {
　　　　if (SiteSet[j] == t_no)
　　　　　SiteSet[j] = f_no;
　　　}
　　　pathlen += Path[i].length;
　　}
　}
　printf("%d\n",pathlen/100);
　　return 0;
}

[192 デフォルトの名無しさん NG NG]

うわ、2回送信しちゃった

[193 デフォルトの名無しさん NG NG]

ちょっと間違い。

　　　pathlen += Path[i].length;

は

　　　pathlen += Path[i].length-1;

だね。