結果

問題 No.519 アイドルユニット
コンテスト
ユーザー snrnsidy
提出日時 2021-06-12 01:52:46
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,295 bytes
コンパイル時間 4,630 ms
コンパイル使用メモリ 203,992 KB
最終ジャッジ日時 2025-01-22 07:36:34
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22 TLE * 12
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void augment()’:
main.cpp:86:13: warning: ‘root’ may be used uninitialized [-Wmaybe-uninitialized]
   86 |         int root;
      |             ^~~~
main.cpp:175:49: warning: ‘x’ may be used uninitialized [-Wmaybe-uninitialized]
  175 |                 for (int cx = x, cy = y, ty; cx != -2; cx = Prev[cx], cy = ty)
      |                                              ~~~^~~~~
main.cpp:110:13: note: ‘x’ was declared here
  110 |         int x, y;
      |             ^

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

#define N 25
#define INF 1e9

int cost[N][N];
int n, max_match;
int lx[N], ly[N];
int xy[N];
int yx[N];
bool S[N], T[N];
int slack[N];
int slackx[N];
int Prev[N];
int board[24][24];

void init_labels()
{
	memset(lx, 0, sizeof(lx));
	memset(ly, 0, sizeof(ly));
	for (int x = 0; x < n; x++)
	{
		for (int y = 0; y < n; y++)
		{
			lx[x] = max(lx[x], cost[x][y]);
		}
	}
}

void update_labels()
{
	int delta = INF;
	for (int y = 0; y < n; y++)
	{
		if (!T[y])
		{
			delta = min(delta, slack[y]);
		}
	}
	for (int x = 0; x < n; x++)
	{
		if (S[x])
		{
			lx[x] -= delta;
		}
	}
	for (int y = 0; y < n; y++)
	{
		if (T[y])
		{
			ly[y] += delta;
		}
	}
	for (int y = 0; y < n; y++)
	{
		if (!T[y])
		{
			slack[y] -= delta;
		}
	}
}

void add_to_tree(int x, int prevx)
{
	S[x] = true;
	Prev[x] = prevx;

	for (int y = 0; y < n; y++)
	{
		if (lx[x] + ly[y] - cost[x][y] < slack[y])
		{
			slack[y] = lx[x] + ly[y] - cost[x][y];
			slackx[y] = x;
		}
	}
}

void augment()
{
	if (max_match == n)
	{
		return;
	}
	int root;
	queue <int> que;
	memset(S, false, sizeof(S));
	memset(T, false, sizeof(T));
	memset(Prev, -1, sizeof(Prev));

	for (int x = 0; x < n; x++)
	{
		if (xy[x] == -1)
		{
			root = x;
			que.push(root);
			Prev[x] = -2;
			S[x] = true;
			break;
		}
	}

	for (int y = 0; y < n; y++)
	{
		slack[y] = lx[root] + ly[y] - cost[root][y];
		slackx[y] = root;
	}

	int x, y;
	while (true)
	{
		while (!que.empty())
		{
			x = que.front();
			que.pop();
			for (y = 0; y < n; y++)
			{
				if (cost[x][y] == lx[x] + ly[y] && !T[y])
				{
					if (yx[y] == -1)
					{
						break;
					}
					T[y] = true;
					que.push(yx[y]);
					add_to_tree(yx[y], x);
				}
				if (y < n)
				{
					break;
				}
			}
			if (y < n)
			{
				break;
			}
		}

		update_labels();
		while (!que.empty())
		{
			que.pop();
		}

		for (y = 0; y < n; y++)
		{
			if (!T[y] && slack[y] == 0)
			{
				if (yx[y] == -1)
				{
					x = slackx[y];
					break;
				}
				else
				{
					T[y] = true;
					if (!S[yx[y]])
					{
						que.push(yx[y]);
						add_to_tree(yx[y], slackx[y]);
					}
				}
			}
		}
		if (y < n)
		{
			break;
		}
	}

	if (y < n)
	{
		max_match++;
		for (int cx = x, cy = y, ty; cx != -2; cx = Prev[cx], cy = ty)
		{
			ty = xy[cx];
			yx[cy] = cx;
			xy[cx] = cy;
		}
		augment();
	}
}

int hungarian()
{
	int res = 0;
	max_match = 0;

	memset(xy, -1, sizeof(xy));
	memset(yx, -1, sizeof(yx));

	init_labels();
	augment();

	for (int x = 0; x < n; x++)
	{
		res += cost[x][xy[x]];
	}

	return res;
}

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int 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 res = 0;

	do
	{
		vector <int> a, b;
		for (int i = 0; i < m; i++)
		{
			if (perm[i] == 0)
			{
				a.push_back(i);
			}
			else
			{
				b.push_back(i);
			}
		}
		memset(cost, 0, sizeof(cost));
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				cost[i][j] = board[a[i]][b[j]];
			}
		}
		res = max(res, hungarian());
	} while (next_permutation(perm.begin(), perm.end()));

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