CodeForces 650C Table Compression

Posted on By 二价氢

题目大意

给定一个矩阵,要求在保证每行与每列相对大小不变的情况下使每个元素最小。

做法

其实是一个染色问题,不是么?就按照染色的贪心来就好了。

对于将所有数从小到大排序之后,找到每个数最小能填的数字,然后可以用并查集或者别的什么数据结构来维护相同的数。

总的复杂度是

代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, pii> vp;

#define x first
#define y second

const int maxn = 1000000 + 1;
int fa[maxn];
int fval[maxn];

int fin(int x) {return fa[x] = ((fa[x] == x) ? x : fin(fa[x]));}

void uni(int x, int y) {
	int fx = fin(x);
	int fy = fin(y);
	if (fx == 0 || fy == 0) return;
	fa[fy] = fx;
}

int main() {
	ios::sync_with_stdio(0);
	vector< vector<int> > v;
	vector< vp > ve;
	vector< pii > row_max, col_max;
	vector< int > row_max_id, col_max_id;
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		v.push_back(vector<int>(m, 0));
	for (int i = 0; i < n; i++)
		row_max.push_back(pii(0, 0)),
		row_max_id.push_back(0);
	for (int i = 0; i < m; i++)
		col_max.push_back(pii(0, 0)),
		col_max_id.push_back(0);
	int cn = 1;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			fa[cn] = cn;
			v[i][j] = cn++;
			int vl;
			cin >> vl;
			ve.push_back(make_pair(vl, make_pair(i, j)));
		}
	sort(ve.begin(), ve.end());
	for (auto val : ve) {
		pii tr = row_max[val.y.x];int vr = fval[fin(row_max_id[val.y.x])];
		pii tc = col_max[val.y.y];int vc = fval[fin(col_max_id[val.y.y])];
		int vl = max(val.x == tr.y ? vr : vr + 1, 
					 val.x == tc.y ? vc : vc + 1);
		if (tr.y == val.x) uni(v[val.y.x][val.y.y], row_max_id[val.y.x]);
		if (tc.y == val.x) uni(v[val.y.x][val.y.y], col_max_id[val.y.y]);
		row_max[val.y.x] = pii(vl, val.x);
		col_max[val.y.y] = pii(vl, val.x);
		col_max_id[val.y.y] = row_max_id[val.y.x] = v[val.y.x][val.y.y];
		fval[fin(v[val.y.x][val.y.y])] = vl;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			cout << fval[fin(v[i][j])] << ' ';
		cout << '\n';
	}
	return 0;
}