#include #include #include #include #include #include #include // 内部定数 #define D_ON 1 // 汎用フラグ - ON #define D_OFF 0 // 汎用フラグ - OFF #define D_FLY_MAX 1000 // 最大飛行数 #define D_ETIME_MAX 1000000000 // 最大到着時間 #define D_VTX_MAX (D_FLY_MAX * 2 + 5) // 最大頂点数((出発時間 + 到着時間) * 飛行数 + 街1 + 街N) #define D_EDGE_MAX D_FLY_MAX + 5 // 最大辺数 // 内部構造体 - 飛行情報 typedef struct Fly { int miTFNo; // 出発街 0~ int miTTNo; // 到着街 0~ int miTimeS; // 出発時間 int miTimeE; // 到着時間+乗り継ぎ時間 int miHCnt; // 飛行人数 } Fly; // 内部構造体 - 辺情報 typedef struct Edge { long long mlCap; // 容量 int miVNo; // 接続先頂点 int miENo; // 接続先頂点の辺 } Edge; // 内部構造体 - 頂点情報 typedef struct Vtx { int miTNo; // 街 int miTime; // 時間 Edge mz1Edge[D_EDGE_MAX]; // 辺 int miECnt; // 辺数 int miDone; // 処理済フラグ } Vtx; // 内部変数 static FILE *szpFpI; // 入力 static Fly sz1Fly[D_FLY_MAX]; // 飛行情報 static int siFCnt; // 飛行情報数 static Vtx sz1Vtx[D_VTX_MAX]; // 頂点 static int siVCnt; // 頂点数 // 内部変数 - テスト用 #ifdef D_TEST static int siRes; static FILE *szpFpA; #endif // ソート関数 - 街昇順 - 時間昇順 int fSortFnc( const void *pzpVal1 // 値1 , const void *pzpVal2 // 値2 ) { Vtx *lzpVal1 = (Vtx *)pzpVal1; Vtx *lzpVal2 = (Vtx *)pzpVal2; // 街昇順 if (lzpVal1->miTNo > lzpVal2->miTNo) { return 1; } else if (lzpVal1->miTNo < lzpVal2->miTNo) { return -1; } // 時間昇順 if (lzpVal1->miTime > lzpVal2->miTime) { return 1; } else if (lzpVal1->miTime < lzpVal2->miTime) { return -1; } return 0; } // 頂点 - 辺 - 追加 int fAddEdge( int piVFNo // 頂点 - 元 0~ , int piVTNo // 頂点 - 先 0~ , long long plEdge // 容量 ) { // 頂点(元)側 Edge *lzpEdge = &sz1Vtx[piVFNo].mz1Edge[sz1Vtx[piVFNo].miECnt]; lzpEdge->mlCap = plEdge; lzpEdge->miVNo = piVTNo; lzpEdge->miENo = sz1Vtx[piVTNo].miECnt; sz1Vtx[piVFNo].miECnt++; // 頂点(先)側 lzpEdge = &sz1Vtx[piVTNo].mz1Edge[sz1Vtx[piVTNo].miECnt]; lzpEdge->mlCap = 0; lzpEdge->miVNo = piVFNo; lzpEdge->miENo = sz1Vtx[piVFNo].miECnt - 1; sz1Vtx[piVTNo].miECnt++; return 0; } // 頂点 - 検索 int fSrhVNo( int piTNo // 街 0~ , int piTime // 時間 ) { int i; for (i = 0; i < siVCnt; i++) { if (sz1Vtx[i].miTNo == piTNo) { if (sz1Vtx[i].miTime == piTime) { return i; } } } return -1; } // 最大流 - 取得 - 1フロー long long fGetMaxFlowOne( int piVSNo // 始点 , int piVENo // 終点 , long long plFlow // 流量 ) { int i; // 処理済フラグ if (sz1Vtx[piVSNo].miDone != D_OFF) { return 0; } sz1Vtx[piVSNo].miDone = D_ON; // 到着チェック if (piVSNo == piVENo) { return plFlow; } // 移動 for (i = 0; i < sz1Vtx[piVSNo].miECnt; i++) { Edge *lzpEdge = &sz1Vtx[piVSNo].mz1Edge[i]; // 流量 long long llFlow = lzpEdge->mlCap; if (llFlow < 1) { // なし continue; } if (llFlow > plFlow) { llFlow = plFlow; } // 下位へ llFlow = fGetMaxFlowOne(lzpEdge->miVNo, piVENo, llFlow); if (llFlow < 1) { // なし continue; } // 流量 - 加算・減算 lzpEdge->mlCap -= llFlow; sz1Vtx[lzpEdge->miVNo].mz1Edge[lzpEdge->miENo].mlCap += llFlow; return llFlow; } return 0; } // 最大流 - 取得 long long fGetMaxFlow( int piVSNo // 始点 , int piVENo // 終点 ) { int i; long long llSum = 0; while (1) { // 処理済フラグ - 初期化 for (i = 0; i < siVCnt; i++) { sz1Vtx[i].miDone = D_OFF; } // 1フロー - 取得 long long llFlow = fGetMaxFlowOne(piVSNo, piVENo, LLONG_MAX); if (llFlow < 1) { // なし break; } // 流量 - 加算 llSum += llFlow; } return llSum; } // 実行メイン int fMain( int piTNo // テスト番号 1~ ) { int i; char lc1Buf[1024], lc1Out[1024]; // データ - 初期化 memset(sz1Vtx, 0, sizeof(sz1Vtx)); // 頂点 // 入力 - セット #ifdef D_TEST sprintf(lc1Buf, ".\\Test\\T%d.txt", piTNo); szpFpI = fopen(lc1Buf, "r"); sprintf(lc1Buf, ".\\Test\\A%d.txt", piTNo); szpFpA = fopen(lc1Buf, "r"); siRes = 0; #else szpFpI = stdin; #endif // 街数・飛行数・乗り継ぎ時間 - 取得 int liTCnt, liTimeA; fgets(lc1Buf, sizeof(lc1Buf), szpFpI); sscanf(lc1Buf, "%d%d%d", &liTCnt, &siFCnt, &liTimeA); // 頂点 - 街1 sz1Vtx[0].miTNo = 0; sz1Vtx[0].miTime = -1; siVCnt = 1; // 飛行 - 取得 for (i = 0; i < siFCnt; i++) { int liFNo, liTNo, liTimeS, liTimeE, liHCnt; fgets(lc1Buf, sizeof(lc1Buf), szpFpI); sscanf(lc1Buf, "%d%d%d%d%d", &liFNo, &liTNo, &liTimeS, &liTimeE, &liHCnt); liFNo--; liTNo--; liTimeE += liTimeA; // 到着時間チェック if (liTimeE > D_ETIME_MAX) { continue; } // 飛行情報 - セット sz1Fly[i].miTFNo = liFNo; sz1Fly[i].miTTNo = liTNo; sz1Fly[i].miTimeS = liTimeS; sz1Fly[i].miTimeE = liTimeE; sz1Fly[i].miHCnt = liHCnt; // 頂点 - 追加 sz1Vtx[siVCnt].miTNo = liFNo; sz1Vtx[siVCnt].miTime = liTimeS; siVCnt++; sz1Vtx[siVCnt].miTNo = liTNo; sz1Vtx[siVCnt].miTime = liTimeE; siVCnt++; } // 頂点 - 街N sz1Vtx[siVCnt].miTNo = liTCnt - 1; sz1Vtx[siVCnt].miTime = INT_MAX; siVCnt++; // 頂点 - ソート qsort(sz1Vtx, siVCnt, sizeof(Vtx), fSortFnc); // 頂点 - 容量 - セット - 同一街 for (i = 0; i < siVCnt - 1; i++) { if (sz1Vtx[i].miTNo == sz1Vtx[i + 1].miTNo) { fAddEdge(i, i + 1, LLONG_MAX); } } // 頂点 - 容量 - セット - 飛行 for (i = 0; i < siFCnt; i++) { // 頂点 - 取得 int liVFNo = fSrhVNo(sz1Fly[i].miTFNo, sz1Fly[i].miTimeS); // 出発 int liVTNo = fSrhVNo(sz1Fly[i].miTTNo, sz1Fly[i].miTimeE); // 到着 // 容量 - セット fAddEdge(liVFNo, liVTNo, sz1Fly[i].miHCnt); } // 最大流 - 取得 long long llMax = fGetMaxFlow(0, siVCnt - 1); // 結果 - セット sprintf(lc1Out, "%lld\n", llMax); // 結果 - 表示 #ifdef D_TEST fgets(lc1Buf, sizeof(lc1Buf), szpFpA); if (strcmp(lc1Buf, lc1Out)) { siRes = -1; } #else printf("%s", lc1Out); #endif // 残データ有無 #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", piTNo); } else { printf("NG %d\n", piTNo); } #endif return 0; } int main() { #ifdef D_TEST int i; for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) { fMain(i); } #else fMain(0); #endif return 0; }