結果

問題 No.519 アイドルユニット
コンテスト
ユーザー kopricky
提出日時 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});
      |                                             ~~~~~~~~~~~~~~^~

ソースコード

diff # 

#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;
}
0