清华集训2014 day2 task3 矩阵变换

题目

算法 稳定婚姻系统（其实就是贪心）

一个方案不合法，当且仅当下面这种情况：

设第\(i\)行选了数字\(x\)，如果第\(j\)行有一个\(x\)在第\(i\)行的\(x\)后面，并且第\(j\)行所选的数字在第\(j\)行的\(x\)后面。

分析到这里就是典型的稳定婚姻系统了。

代码

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <assert.h>

using namespace std;

#ifdef debug

#define ep(...) fprintf(stderr, __VA_ARGS__)

#else

#define ep(...) assert(true)

#endif

	template <class T>

void relax(T &a, const T &b)

{

	if (b > a) a = b;

}

	template <class T>

void tension(T &a, const T &b)

{

	if (b < a) a = b;

}

int geti()

{

	int ret = 0;

	char ch = getchar();

	while (ch < '0' || ch > '9') ch = getchar();

	do

	{

		ret = ret * 10 + (int) ch - 48;

		ch = getchar();

	}while (ch >= '0' && ch <= '9');

	return ret;

}

const int MaxN = 203;

const int MaxM = 403;

int n, m;

int A[MaxN][MaxM];

void output(const int *x)

{

	ep("answer ");

	for (int i = 0; i < n; i ++)

	{

		printf("%d ", x[i]);

		ep("%d ", x[i]);

	}

	printf("\n");

	ep("\n");

}

void output_nosolution()

{

	ep("no solution\n");

	printf("\\\n");

}

int posi[MaxN][MaxN];

int choice[MaxN];

void next_choice(const int &i)

{

	int &tmp = choice[i];

	tmp ++;

	while (tmp < m && A[i][tmp] == 0)

		tmp ++;

	if (tmp >= m) tmp = -1;

}

void Main()

{

	n = geti();

	m = geti();

	for (int i = 0; i < n; i ++)

		for (int j = 0; j < m; j ++)

		{

			A[i][j] = geti();

			if (A[i][j])

				posi[i][ A[i][j] ] = j;

		}

	{

		for (int i = 0; i < n; i ++)

		{

			choice[i] = -1;

			next_choice(i);

		}

		static int row_love[MaxN], num_love[MaxN];

		for (int i = 0; i < n; i ++)

			row_love[i] = num_love[i + 1] = -1;

		int cnt = 0;

		while (cnt < n)

		{

			for (int i = 0; i < n; i ++)

			{

				if (row_love[i] == -1)

				{

					int num = A[i][choice[i]];

					assert(num != -1);

					next_choice(i);

					if (num_love[num] == -1)

					{

						cnt ++;

						row_love[i] = num;

						num_love[num] = i;

					}

					else if (posi[i][num] > posi[ num_love[num] ][num])

					{

						row_love[num_love[num]] = -1;

						row_love[i] = num;

						num_love[num] = i;

					}

				}

			}

		}

		output(row_love);

	}

}

int main()

{

#if defined(debug) || defined(local)

	freopen("c.in", "r", stdin);

	freopen("c.out", "w", stdout);

#endif

	int cases = geti();

	for (int i = 0; i < cases; i ++)

		Main();

	return 0;

}