結果
問題 | No.519 アイドルユニット |
ユーザー |
|
提出日時 | 2017-07-16 22:24:28 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,835 bytes |
コンパイル時間 | 1,515 ms |
コンパイル使用メモリ | 168,772 KB |
実行使用メモリ | 16,712 KB |
最終ジャッジ日時 | 2024-10-08 04:34:06 |
合計ジャッジ時間 | 6,144 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | TLE * 1 -- * 33 |
コンパイルメッセージ
main.cpp: In function ‘void add_edge(int, int, int, int)’: main.cpp:30:56: warning: narrowing conversion of ‘G[to].std::vector<edge>::size()’ from ‘std::vector<edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing] 30 | G[from].push_back((edge){to,cap,cost,G[to].size()}); | ~~~~~~~~~~^~ main.cpp:31:59: warning: narrowing conversion of ‘(G[from].std::vector<edge>::size() - 1)’ from ‘std::vector<edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing] 31 | G[to].push_back((edge){from,0,-cost,G[from].size()-1}); | ~~~~~~~~~~~~~~^~
ソースコード
#include <bits/stdc++.h> #define ll long long #define INF 1000000005 #define MOD 1000000007 #define EPS 1e-10 #define rep(i,n) for(int i=0;i<(int)n;++i) #define each(a, b) for(auto (a): (b)) #define all(v) (v).begin(),(v).end() #define fi first #define se second #define pb push_back #define show(x) cout <<#x<<" = "<<(x)<<endl #define spair(p) cout <<#p<<": "<<p.fi<<" "<<p.se<<endl #define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl #define sset(s) cout<<#s<<":";each(kbrni,s)cout <<" "<<kbrni;cout<<endl using namespace std; typedef pair<int,int>P; const int MAX_V = 26; struct edge{ int to,cap,cost,rev; //行き先,容量,費用,逆辺 }; vector<edge> G[MAX_V]; void add_edge(int from,int to,int cap,int cost){ G[from].push_back((edge){to,cap,cost,G[to].size()}); G[to].push_back((edge){from,0,-cost,G[from].size()-1}); } int min_cost_flow(const int vcnt,const int s,const int t,int f) { int res =0; int dist[MAX_V]; int prevv[MAX_V]; int preve[MAX_V]; while(f>0){ fill(dist,dist+vcnt,INF); dist[s] = 0; bool update = true; while(update){ update = false; for(int v=0;v<vcnt;v++){ if(dist[v] == INF) continue; for(int i=0;i<G[v].size();i++){ edge &e = G[v][i]; if(e.cap > 0 && dist[e.to] > dist[v] + e.cost){ dist[e.to] = dist[v] + e.cost; prevv[e.to] = v; //一つ前の頂点を記憶 preve[e.to] = i; //枝の番目を記憶 update = true; } } } } if(dist[t] == INF){ return -1; } int d = f; for(int v=t;v!=s;v=prevv[v]){ d = min(d,G[prevv[v]][preve[v]].cap); } f -= d; res += d * dist[t]; for(int v=t;v!=s;v=prevv[v]){ edge &e = G[prevv[v]][preve[v]]; e.cap -= d; G[v][e.rev].cap += d; } } return res; } int deg[MAX_V][MAX_V]; int main() { int n; cin >> n; rep(i,n){ rep(j,n){ cin >> deg[i][j]; } } int N = n-1; int ans = INF; vector<bool> v(N); fill(v.end() - (n/2 - 1), v.end(), true); do { vector<int> res1,res2; rep(i,n+2){ G[i].clear(); } rep(i,N) { if (v[i]) { res1.pb(i); }else{ res2.pb(i); } } add_edge(0,1,1,0); rep(i,res2.size()){ add_edge(1,res2[i]+2,INF,-deg[0][res2[i]+1]); } rep(i,res1.size()){ add_edge(0,res1[i]+2,1,0); } rep(i,res1.size()){ rep(j,res2.size()){ add_edge(res1[i]+2,res2[j]+2,INF,-deg[res1[i]+1][res2[j]+1]); } } rep(i,res2.size()){ add_edge(res2[i]+2,n+1,1,0); } ans = min(ans,min_cost_flow(n+2,0,n+1,n/2)); } while (next_permutation(v.begin(), v.end())); cout << -ans << endl; return 0; }