結果

問題 No.748 yuki国のお財布事情
コンテスト
ユーザー asugen0402
提出日時 2019-05-16 11:44:11
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 79 ms / 2,000 ms
コード長 4,204 bytes
コンパイル時間 190 ms
コンパイル使用メモリ 32,896 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-17 05:27:12
合計ジャッジ時間 3,399 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部定数
#define D_TOWN_MAX		100000									// 最大町数
#define D_ROAD_MAX		100000									// 最大道路数

// 内部構造体 - 道路情報
typedef struct Road {
	int miTNo1;													// 町１
	int miTNo2;													// 町２
	int miCost;													// コスト
} Road;

// 内部変数
static FILE *szpFpI;											// 入力
static int siTCnt;												// 町数
static Road sz1Road[D_ROAD_MAX];								// 道路
static int siRCnt;												// 道路数
static int si1GNo[D_TOWN_MAX];									// 代表町番号[町] 0～
static int siGCnt;												// 代表町番号数
static long long slSum;											// 削減維持費合計

// 内部変数 - テスト用
#ifdef D_TEST
	static int siRes;
	static FILE *szpFpA;
	static int siTNo;
#endif

// 出力
int
fOut(
	char *pcpLine				// <I> １行
)
{
	char lc1Buf[1024];

#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, pcpLine)) {
		siRes = -1;
	}
#else
	printf("%s", pcpLine);
#endif

	return 0;
}

// ソート関数 - コスト昇順
int
fSortFnc(
	const void *pzpVal1			// <I> 値１
	, const void *pzpVal2		// <I> 値２
)
{
	Road *lzpVal1 = (Road *)pzpVal1;
	Road *lzpVal2 = (Road *)pzpVal2;

	// コスト昇順
	if (lzpVal1->miCost > lzpVal2->miCost) {
		return 1;
	}
	else if (lzpVal1->miCost < lzpVal2->miCost) {
		return -1;
	}

	return 0;
}

// 代表町番号 - 取得
int
fGetGNo(
	int piTNo					// <I> 町番号 0～
)
{
	// 代表チェック
	if (piTNo == si1GNo[piTNo]) {
		return piTNo;
	}

	// 下位へ
	si1GNo[piTNo] = fGetGNo(si1GNo[piTNo]);

	return si1GNo[piTNo];
}

// 道路 - 追加
int
fAddRoad(
	int piMode					// <I> [1]:強制 [2]:必要時
	, int piRNo					// <I> 道路 0～
)
{
	// 代表町番号 - 取得
	int liGNo1 = fGetGNo(sz1Road[piRNo].miTNo1);
	int liGNo2 = fGetGNo(sz1Road[piRNo].miTNo2);

	// 削減維持費合計 - 減算
	if (piMode == 1 || liGNo1 != liGNo2) {
		slSum -= sz1Road[piRNo].miCost;

		// 町 - 結合
		if (liGNo1 != liGNo2) {
			si1GNo[liGNo1] = liGNo2;
			siGCnt--;
		}
	}

	return 0;
}

// 実行メイン
int
fMain(
)
{
	int i;
	char lc1Buf[1024];

	// 町数・道路数・削除不可道路数 - 取得
	int liRCnt;
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%d%d%d", &siTCnt, &siRCnt, &liRCnt);

	// 代表町番号 - 初期化
	siGCnt = siTCnt;
	for (i = 0; i < siGCnt; i++) {
		si1GNo[i] = i;
	}

	// 道路 - 取得
	for (i = 0; i < siRCnt; i++) {
		fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
		sscanf(lc1Buf, "%d%d%d", &sz1Road[i].miTNo1, &sz1Road[i].miTNo2, &sz1Road[i].miCost);
		sz1Road[i].miTNo1--;
		sz1Road[i].miTNo2--;
		slSum += sz1Road[i].miCost;
	}

	// 削除不可道路 - 追加
	for (i = 0; i < liRCnt; i++) {
		int liRNo;
		fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
		sscanf(lc1Buf, "%d", &liRNo);
		fAddRoad(1, liRNo - 1);
	}

	// 道路 - ソート
	qsort(sz1Road, siRCnt, sizeof(Road), fSortFnc);

	// 道路 - 追加
	for (i = 0; i < siRCnt; i++) {
		if (siGCnt < 2) {
			break;
		}
		else {
			fAddRoad(2, i);
		}
	}

	return 0;
}

// １回実行
int
fOne(
)
{
	int liRet;
	char lc1Buf[1024];

	// データ - 初期化
	slSum = 0;													// 削減維持費合計

	// 入力 - セット
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", siTNo);
	szpFpI = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", siTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#else
	szpFpI = stdin;
#endif

	// 実行メイン
	liRet = fMain();

	// 出力
	sprintf(lc1Buf, "%lld\n", slSum);
	fOut(lc1Buf);

	// 残データ有無
#ifdef D_TEST
	lc1Buf[0] = '\0';
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, "")) {
		siRes = -1;
	}
#endif

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpI);
	fclose(szpFpA);
#endif

	// テスト結果
#ifdef D_TEST
	if (siRes == 0) {
		printf("OK %d\n", siTNo);
	}
	else {
		printf("NG %d\n", siTNo);
	}
#endif

	return 0;
}

// プログラム開始
int
main()
{

#ifdef D_TEST
	int i;
	for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
		siTNo = i;
		fOne();
	}
#else
	fOne();
#endif

	return 0;
}
0