結果
問題 | No.519 アイドルユニット |
ユーザー |
![]() |
提出日時 | 2017-06-01 20:17:24 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,958 bytes |
コンパイル時間 | 838 ms |
コンパイル使用メモリ | 90,316 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-21 21:41:51 |
合計ジャッジ時間 | 1,890 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 WA * 7 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:97:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 97 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ main.cpp:102:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 102 | scanf("%d", &fs[i][j]); | ~~~~~^~~~~~~~~~~~~~~~~
ソースコード
/* -*- coding: utf-8 -*- * * 519.cc: No.519 アイドルユニット - yukicoder */ #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<string> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<functional> using namespace std; /* constant */ const int MAX_N = 100; const int INF = 1 << 30; /* typedef */ typedef vector<int> vi; typedef pair<int,int> pii; /* global variables */ int fs[MAX_N][MAX_N]; vi nbrs[MAX_N]; int caps[MAX_N][MAX_N], costs[MAX_N][MAX_N], flows[MAX_N][MAX_N]; /* subroutines */ pii min_cost_flow(const int n, const vi nbrs[], int st, int gl) { // assume that caps and costs are pre-assigned memset(flows, 0, sizeof(flows)); pii total; // (cost, flow) vi hs(n, 0); for (;;) { //printf("total=%d,%d\n", total.first, total.second); vi dists(n, INF); dists[st] = 0; vi prvs(n, -1); vi minfs(n, INF); for (int i = 0; i < n - 1; i++) { for (int ui = 0; ui < n; ui++) { int &ud = dists[ui]; const vi &nbru = nbrs[ui]; for (vi::const_iterator vit = nbru.begin(); vit != nbru.end(); vit++) { const int &vi = *vit; int vc = caps[ui][vi] - flows[ui][vi]; if (vc > 0) { int vd = ud + costs[ui][vi] + hs[ui] - hs[vi]; if (dists[vi] > vd) { dists[vi] = vd; prvs[vi] = ui; minfs[vi] = min(vc, minfs[ui]); } } } } } if (prvs[gl] < 0) break; int min_flow = minfs[gl]; for (int v = gl; v != st;) { int u = prvs[v]; total.first += min_flow * costs[u][v]; flows[u][v] += min_flow; flows[v][u] -= min_flow; v = u; } total.second += min_flow; for (int i = 0; i < n; i++) hs[i] += dists[i]; } return total; } /* main */ int main() { int n; scanf("%d", &n); int maxf = 0; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { scanf("%d", &fs[i][j]); if (maxf < fs[i][j]) maxf = fs[i][j]; } //printf("maxf=%d\n", maxf); int st = n * 2, gl = st + 1, gn = gl + 1; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (i != j && fs[i][j] >= 0) { int f = maxf - fs[i][j]; nbrs[i].push_back(n + j); caps[i][n + j] = 1; costs[i][n + j] = f; nbrs[n + j].push_back(i); caps[n + j][i] = 0; costs[n + j][i] = -f; } for (int i = 0; i < n; i++) { nbrs[st].push_back(i); caps[st][i] = 1; costs[st][i] = 0; nbrs[i].push_back(st); caps[i][st] = 0; costs[i][st] = 0; } for (int i = 0; i < n; i++) { nbrs[n + i].push_back(gl); caps[n + i][gl] = 1; costs[n + i][gl] = 0; nbrs[gl].push_back(n + i); caps[gl][n + i] = 0; costs[gl][n + i] = 0; } pii t = min_cost_flow(gn, nbrs, st, gl); //printf("%d %d\n", t.first, t.second); printf("%d\n", (maxf * n - t.first) / 2); return 0; }