#include #include #include #include #include #include #include // 内部定数 #define D_TOWN_MAX 100000 // 最大町数 #define D_ROAD_MAX 100000 // 最大道路数 // 内部構造体 - 道路情報 typedef struct Road { int miTNo1; // 町1 int miTNo2; // 町2 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 // 1行 ) { 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 // 値1 , const void *pzpVal2 // 値2 ) { 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 // 町番号 0~ ) { // 代表チェック if (piTNo == si1GNo[piTNo]) { return piTNo; } // 下位へ si1GNo[piTNo] = fGetGNo(si1GNo[piTNo]); return si1GNo[piTNo]; } // 道路 - 追加 int fAddRoad( int piMode // [1]:強制 [2]:必要時 , int piRNo // 道路 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; } // 1回実行 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; }