SkyWT / 博客 / CodeForces 274D Lovely Matrix:“冗余点” 建边 + 拓扑

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

2018 年 8 月 6 日 10:41


文章目录

题目链接: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 (1nm105)(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 00 and 10910^9 inclusive) represent filled entries.

Output

If there exists no possible reordering of the columns print -1. Otherwise the output should contain m integers p1,p2,...,pmp_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 p2p_2-th column of the initial matrix and so on.

Examples

Input #1

3 3
1 -1 -1
1 2 1
2 -1 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

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

对于每一行的每一个元素,我们可以在它和第一个比它小的元素之间增加一个“冗余点”,在它和第一个比它大的元素之间也建一个“冗余点”,然后让它与这两个“冗余点”连边。其实具体在实现的时候,我们是对于每行的元素排序做的,这样建边时间复杂度就降到 Θ(NM)\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;
}

暂无评论


发表新的评论

所有评论都将经过博主审核。请勿填写无意义邮箱或发表无关评论、广告等,否则会被视为垃圾评论。

提交评论即表明你同意本网站使用 Cookie,并允许本站在后台记录你的邮箱、IP 地址等必要信息。这些信息不会被透露给其他用户。(提交一次评论后,本提示将不再展示)