清华集训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;
}
上一篇:AC日记——【清华集训2014】奇数国 uoj 38


下一篇:uoj#38. 【清华集训2014】奇数国【欧拉函数】