結果

問題 No.748 yuki国のお財布事情
コンテスト
ユーザー 👑 testestest
提出日時 2018-10-19 21:49:40
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 58 ms / 2,000 ms
コード長 992 bytes
コンパイル時間 180 ms
コンパイル使用メモリ 31,104 KB
実行使用メモリ 7,260 KB
最終ジャッジ日時 2024-11-18 20:24:53
合計ジャッジ時間 1,774 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'main':
main.c:19:9: warning: implicit declaration of function 'scanf' [-Wimplicit-function-declaration]
   19 |         scanf("%d%d%d",&n,&m,&k);
      |         ^~~~~
main.c:1:1: note: include '<stdio.h>' or provide a declaration of 'scanf'
  +++ |+#include <stdio.h>
    1 | //union-find
main.c:19:9: warning: incompatible implicit declaration of built-in function 'scanf' [-Wbuiltin-declaration-mismatch]
   19 |         scanf("%d%d%d",&n,&m,&k);
      |         ^~~~~
main.c:19:9: note: include '<stdio.h>' or provide a declaration of 'scanf'
main.c:35:9: warning: implicit declaration of function 'qsort' [-Wimplicit-function-declaration]
   35 |         qsort(e,m,sizeof(E),edgehikaku);
      |         ^~~~~
main.c:46:9: warning: implicit declaration of function 'printf' [-Wimplicit-function-declaration]
   46 |         printf("%ld",ans);
      |         ^~~~~~
main.c:46:9: note: include '<stdio.h>' or provide a declaration of 'printf'
main.c:46:9: warning: incompatible implicit declaration of built-in function 'printf' [-Wbuiltin-declaration-mismatch]
main.c:46:9: note: include '<stdio.h>' or provide a declaration of 'printf'

ソースコード

diff # 

//union-find
#define LIMIT 100000
int uniroot[LIMIT+10],unicnt[LIMIT+10];
void ufinit(int n){for(int i=0;i<n;i++){uniroot[i]=i;unicnt[i]=1;}}
int root(int x){return uniroot[x]!=x?uniroot[x]=root(uniroot[x]):x;}
int same(int x,int y){return root(x)==root(y);}
void uni(int x,int y){if((x=root(x))==(y=root(y)))return;uniroot[x]=y;unicnt[y]+=unicnt[x];}

typedef struct edge{long s,g,c;}E;
int edgehikaku(const void*a,const void*b){
	E*p=(E*)a,*q=(E*)b;
	if((*p).c<(*q).c)return -1;
	return 1;
}

E e[100010];
int main(){
	int n,m,k;
	scanf("%d%d%d",&n,&m,&k);
	ufinit(n);
	for(int i=0;i<m;i++){
		long a,b,c;
		scanf("%ld%ld%ld",&a,&b,&c);
		e[i].s=a-1;
		e[i].g=b-1;
		e[i].c=c;
	}
	for(int i=0;i<k;i++){
		int t;
		scanf("%d",&t);
		t--;
		e[t].c=2000000000;
		uni(e[t].s,e[t].g);
	}
	qsort(e,m,sizeof(E),edgehikaku);
	
	long ans=0;
	for(int i=0;i<m;i++){
		if(same(e[i].s,e[i].g)){
			if(e[i].c==2000000000)break;
			ans+=e[i].c;
		}else{
			uni(e[i].s,e[i].g);
		}
	}
	printf("%ld",ans);
}
0