CodeForces 274D Lovely Matrix：“冗余点” 建边 + 拓扑

This blog post is only available in Simplified Chinse.

题目链接：CodeForces 274D Lovely Matrix 今天看CF官方题解的时候学来一句话，暴力解法称为 “The naïve solution” :joy:

Problem

Lenny had an n × m matrix of positive integers. He loved the matrix so much, because each row of the matrix was sorted in non-decreasing order. For the same reason he calls such matrices of integers lovely.

One day when Lenny was at school his little brother was playing with Lenny's matrix in his room. He erased some of the entries of the matrix and changed the order of some of its columns. When Lenny got back home he was very upset. Now Lenny wants to recover his matrix.

Help him to find an order for the columns of the matrix so that it's possible to fill in the erased entries of the matrix to achieve a lovely matrix again. Note, that you can fill the erased entries of the matrix with any integers.

Input

The first line of the input contains two positive integers n and m $(1 ≤ n·m ≤ 10^5)$ . Each of the next n lines contains m space-separated integers representing the matrix. An integer -1 shows an erased entry of the matrix. All other integers (each of them is between $0$ and $10^9$ inclusive) represent filled entries.

Output

If there exists no possible reordering of the columns print -1. Otherwise the output should contain m integers $p_1, p_2, ..., p_m$ showing the sought permutation of columns. So, the first column of the lovely matrix will be p1-th column of the initial matrix, the second column of the lovely matrix will be $p_2$ -th column of the initial matrix and so on.

Examples

Input #1

Output #1

3 1 2

Input #2

2 3
1 2 2
2 5 4

Output #2

1 3 2

Input #3

2 3
1 2 3
3 2 1

Output #3

-1

Translation

给你一个 n 行 m 列的矩阵，其中 -1 可以换成任何数字。要你重新安排这些列的顺序，使得矩阵每行单调不降。如果做不到则输出 -1。

Analysis

看到这题很容易想到是拓扑排序，但是对于每一行我们都需要 $N^2$ 地建边，显然会超时。这时候就要用到一个黑科技：利用冗余点建边。

对于每一行的每一个元素，我们可以在它和第一个比它小的元素之间增加一个“冗余点”，在它和第一个比它大的元素之间也建一个“冗余点”，然后让它与这两个“冗余点”连边。其实具体在实现的时候，我们是对于每行的元素排序做的，这样建边时间复杂度就降到 $\Theta (N\ast M)$ ，但是空间要开两倍（因为增加的“冗余点”也要加入拓扑排序）。这是一种典型的空间换时间的思想。

建边核心代码如下：

inline void Build(int k){ // K 代表当前行，rcd[].x 存储了已经排好序的每行数据
	for (int i=1;i<=m;i++) ans[i].id=i;
	int s=-1;bool fst=true; // fst 标记最小的元素，由于没有比其更小的元素，所以它之前不需要增加冗余点。最大元素也类似。
	while (rcd[k][s+1].x==-1) s++; // 对于-1可以忽略，不加入拓扑排序
	for (int i=s+1;i<m;){ // 排序去重的做法
		int j=i;cnt++;
		if (!fst) add(cnt-1+m,rcd[k][i].id);
		while (rcd[k][j+1].x==rcd[k][i].x&&j+1<m){
			j++;
			if (!fst) add(cnt-1+m,rcd[k][j].id);
		}
		fst=false;
		if (j+1<m) for (int t=i;t<=j;t++) add(rcd[k][t].id,cnt+m);
		i=j+1;
	}
}

Code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=200005,maxe=400005;
int n,m,cnt=0;
int tot=0,lnk[maxn],nxt[maxe],son[maxe],ind[maxe];
struct WT{
	int x,id;
}ans[maxn];
vector<int> a[maxn];
vector<WT> rcd[maxn];
queue<int> que;

inline int read(){
	int ret=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
inline void add(int x,int y){
	x++;y++;
	tot++;ind[y]++;son[tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;
	//printf("Add an edge: %d  -> %d\n",x,y);
}
inline bool cmp(WT aa,WT bb){
	return aa.x<bb.x;
}
inline void Build(int k){
	for (int i=1;i<=m;i++) ans[i].id=i;
	int s=-1;bool fst=true;
	while (rcd[k][s+1].x==-1) s++;
	for (int i=s+1;i<m;){
		int j=i;cnt++;
		if (!fst) add(cnt-1+m,rcd[k][i].id);
		while (rcd[k][j+1].x==rcd[k][i].x&&j+1<m){
			j++;
			if (!fst) add(cnt-1+m,rcd[k][j].id);
		}
		fst=false;
		if (j+1<m) for (int t=i;t<=j;t++) add(rcd[k][t].id,cnt+m);
		i=j+1;
	}
}
inline void Topology(){
	for (int i=1;i<=m;i++) if (ind[i]==0) ans[i].x=1,que.push(i);
	while (!que.empty()){
		int x=que.front();que.pop();
		for (int i=lnk[x];i;i=nxt[i]){
			ind[son[i]]--;
			ans[son[i]].x=max(ans[son[i]].x,ans[x].x+bool(son[i]<=m));
			if (ind[son[i]]==0) que.push(son[i]);
		}
	}
}
int main(){
	n=read();m=read();
	for (int i=1;i<=n;i++){
		for (int j=0;j<m;j++){
			int now=read();
			a[i].push_back(now);
			rcd[i].push_back((WT){now,j});
		}
		sort(rcd[i].begin(),rcd[i].end(),cmp);
	}
	for (int i=1;i<=n;i++) Build(i);
	Topology();
	sort(ans+1,ans+1+m,cmp);
	if (ans[1].x==0){printf("-1\n");return 0;}
	for (int i=1;i<=m;i++) printf("%d ",ans[i].id);
	printf("\n");
	return 0;
}

8/6/2018