#include #include #include #include #include #include #include // 内部定数 #define D_ON 1 // 汎用フラグ - ON #define D_OFF 0 // 汎用フラグ - OFF #define D_VTX_MAX 105 // 最大頂点数 // 内部構造体 - 頂点情報 typedef struct Vtx { int mi1Cap[D_VTX_MAX]; // 容量[接続先頂点] int miDone; // 処理済フラグ } Vtx; // 内部変数 static FILE *szpFpI; // 入力 static Vtx sz1Vtx[D_VTX_MAX]; // 頂点 [0]:開始 [1~GCnt]:原画 [GCnt+1~GCnt+MCnt]:作画 [GCnt+MCnt+1]:終了 static int siVCnt; // 頂点数 // 内部変数 - テスト用 #ifdef D_TEST static int siRes; static FILE *szpFpA; #endif // 最大流 - 取得 - 1フロー int fGetMaxFlowOne( int piVSNo // 始点 , int piVENo // 終点 , int piFlow // 流量 ) { int i; // 処理済フラグ if (sz1Vtx[piVSNo].miDone != D_OFF) { return 0; } sz1Vtx[piVSNo].miDone = D_ON; // 到着チェック if (piVSNo == piVENo) { return piFlow; } // 移動 for (i = 0; i < siVCnt; i++) { // 流量 int liFlow = sz1Vtx[piVSNo].mi1Cap[i]; if (liFlow < 1) { // なし continue; } if (liFlow > piFlow) { liFlow = piFlow; } // 下位へ liFlow = fGetMaxFlowOne(i, piVENo, liFlow); if (liFlow < 1) { // なし continue; } // 流量 - 加算・減算 sz1Vtx[piVSNo].mi1Cap[i] -= liFlow; sz1Vtx[i].mi1Cap[piVSNo] += liFlow; return liFlow; } return 0; } // 最大流 - 取得 int fGetMaxFlow( int piVSNo // 始点 , int piVENo // 終点 ) { int i; int liSum = 0; while (1) { // 処理済フラグ - 初期化 for (i = 0; i < siVCnt; i++) { sz1Vtx[i].miDone = D_OFF; } // 1フロー - 取得 int liFlow = fGetMaxFlowOne(piVSNo, piVENo, INT_MAX); if (liFlow < 1) { // なし break; } // 流量 - 加算 liSum += liFlow; } return liSum; } // 実行メイン int fMain( int piTNo // テスト番号 1~ ) { int i, j; 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 liCCnt; fgets(lc1Buf, sizeof(lc1Buf), szpFpI); sscanf(lc1Buf, "%d", &liCCnt); // 原画数 - 取得 int liGCnt; fgets(lc1Buf, sizeof(lc1Buf), szpFpI); sscanf(lc1Buf, "%d", &liGCnt); // 開始 -> 原画 for (i = 0; i < liGCnt; i++) { sz1Vtx[0].mi1Cap[i + 1] = INT_MAX; } // 原画 - 取得 int liGVal[D_VTX_MAX]; for (i = 0; i < liGCnt; i++) { fscanf(szpFpI, "%d", &liGVal[i]); } fgets(lc1Buf, sizeof(lc1Buf), szpFpI); // 作画数 - 取得 int liMCnt; fgets(lc1Buf, sizeof(lc1Buf), szpFpI); sscanf(lc1Buf, "%d", &liMCnt); // 頂点数 siVCnt = liGCnt + liMCnt + 2; // 原画 -> 作画 for (i = 0; i < liGCnt; i++) { for (j = 0; j < liMCnt; j++) { sz1Vtx[i + 1].mi1Cap[liGCnt + j + 1] = liGVal[i]; } } // 作画 - 取得 for (i = 0; i < liMCnt; i++) { int liMVal; fscanf(szpFpI, "%d", &liMVal); // 作画 -> 終了 sz1Vtx[liGCnt + i + 1].mi1Cap[siVCnt - 1] = liMVal; } fgets(lc1Buf, sizeof(lc1Buf), szpFpI); // 合わない原画数 - 取得 for (i = 0; i < liMCnt; i++) { int liNCnt; fscanf(szpFpI, "%d", &liNCnt); // 合わない原画 - 取得 for (j = 0; j < liNCnt; j++) { int liNVal; fscanf(szpFpI, "%d", &liNVal); // 原画 -> 作画 - クリア sz1Vtx[liNVal].mi1Cap[liGCnt + i + 1] = 0; } fgets(lc1Buf, sizeof(lc1Buf), szpFpI); } // 最大流 - 取得 int liMax = fGetMaxFlow(0, siVCnt - 1); // 結果 - セット if (liMax >= liCCnt) { sprintf(lc1Out, "SHIROBAKO\n"); } else { sprintf(lc1Out, "BANSAKUTSUKITA\n"); } // 結果 - 表示 #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; }