結果

問題 No.519 アイドルユニット
コンテスト
ユーザー snrnsidy
提出日時 2021-06-12 02:23:21
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,664 bytes
コンパイル時間 2,305 ms
コンパイル使用メモリ 206,288 KB
最終ジャッジ日時 2025-01-22 07:37:59
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22 TLE * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

const int N = 26;
const int S = N - 2;
const int E = N - 1;
const int INF = 1000000000;

int n, m;
int c[N][N] = { 0, };
int d[N][N] = { 0, };
int f[N][N] = { 0, };
vector <int> adj[N];
int board[25][25];

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int n,m;

	cin >> m;

	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> board[i][j];
		}
	}
	n = m / 2;
	vector <int> perm(m, 0);
	for (int i = 0; i < n; i++)
	{
		perm[i] = 1;
	}

	sort(perm.begin(), perm.end());

	int ret = 0;

	do
	{
		memset(c, 0, sizeof(c));
		memset(d, 0, sizeof(d));
		for (int i = 0; i < N; i++)
		{
			adj[i].clear();
		}
		vector <int> a, b;
		for (int i = 0; i < m; i++)
		{
			if (perm[i] == 0)
			{
				a.push_back(i);
			}
			else
			{
				b.push_back(i);
			}
		}
		for (int i = 0;i<a.size(); i++)
		{
			c[S][a[i]] = 1;
			d[S][a[i]] = 0;
			d[a[i]][S] = 0;

			adj[S].push_back(a[i]);
			adj[a[i]].push_back(S);
		}
		for (int i = 0;i<b.size();i++)
		{
			c[b[i]][E] = 1;
			d[b[i]][E] = 0;
			d[E][b[i]] = 0;

			adj[b[i]].push_back(E);
			adj[E].push_back(b[i]);
		}
		for (int i = 0; i < a.size(); i++)
		{
			for (int j = 0; j < b.size(); j++)
			{
				//cout << a[i] << ' ' << b[j] << ' ' << board[a[i]][b[j]] << '\n';
				adj[a[i]].push_back(b[j]);
				adj[b[j]].push_back(a[i]);
				d[a[i]][b[j]] = -board[a[i]][b[j]];
				d[b[j]][a[i]] = board[a[i]][b[j]];
				c[a[i]][b[j]] = 1;
			}
		}

		int res = 0;
		int cnt = 0;

		memset(f, 0, sizeof(f));
		while (1)
		{
			int prev[N], dist[N];
			bool inqueue[N];
			memset(inqueue, false, sizeof(inqueue));
			queue <int> que;
			memset(prev, -1, sizeof(prev));

			for (int i = 0; i < N; i++)
			{
				dist[i] = 1e9;
			}

			que.push(S);
			dist[S] = 0;
			inqueue[S] = true;
			while (!que.empty())
			{
				int now = que.front();
				que.pop();

				inqueue[now] = false;
				for (auto next : adj[now])
				{
					//cout << now << ' ' << next << ' ' << c[now][next] << ' ' << f[now][next] << ' ' << dist[now] << ' ' << dist[next] << ' ' << d[now][next] << '\n';
					if (c[now][next] - f[now][next] > 0 && dist[next] > dist[now] + d[now][next])
					{
						dist[next] = dist[now] + d[now][next];
						prev[next] = now;

						if (!inqueue[next])
						{
							que.push(next);
							inqueue[next] = true;
						}
					}
				}
			}

			if (prev[E] == -1)
			{
				break;
			}

			for (int i = E; i != S; i = prev[i])
			{
				res += d[prev[i]][i];
				f[prev[i]][i]++;
				f[i][prev[i]]--;
			}
			cnt++;
		}
		ret = max(ret, abs(res));
	} while (next_permutation(perm.begin(), perm.end()));

	cout << ret << '\n';
	return 0;
}
0