2018.08.29 NOIP模拟 table（拓扑排序+建图优化）

【描述】

给出一个表格，N 行 M 列，每个格子有一个整数，有些格子是空的。现在需要你

来做出一些调整，使得每行都是非降序的。这个调整只能是整列的移动。

【输入】

第一行两个正整数 N 和 M。

接下来 N 行，每行 M 个整数，-1 表示这个格子是空的，其他的整数都在 [0, 10^9]范围，表示格子的数字。

【输出】

若无解，输出 -1；

否则输出任意一个解，即一行 M 个正整数 p1, p2, · · · , pm，表示可以把初始表格的 pi 列，放在新表格的第 i 列，以得到一个合法的表格。

【样例输入 1】

3 3

-1 -1 -1

2 1 2

2 -1 1

【样例输出 1】

2 3 1

【样例输入 2】

2 2

1 2

2 1

【样例输出 2】

-1

对于 20% 的数据，满足 1 ≤ N ≤ 8，1 ≤ M ≤ 8。

对于 60% 的数据，满足 1 ≤ N × M ≤ 2 × 10^3。

对于 100% 的数据，满足 1 ≤ N × M ≤ 10^5。

听说是最难的一道，但被xly大佬用爆搜跑过去了（能把spj卡爆太强了%%%）。

正解貌似很好想，题目无非就是让我们判定一堆列的相对关系，这个可以用有向边来表示，这样的话如果出现环就说明情况不合法。

但是会有一堆相同的数字出现，如何处理？

我们对于一堆相同的数字建一个虚点，然后将这些数字给它连边就行了。

代码：

#include<bits/stdc++.h>
#define N 1000005
using namespace std;
inline int read(){
    int ans=0,w=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    return ans*w;
}
int n,m,ans[N],first[N],cnt=0,tot=0,hd,tl,du[N];
struct edge{int v,next;}e[N*20];
struct Node{int v,id;}q[N];
bool vis[N],in[N];
inline bool cmp(Node a,Node b){return a.v<b.v;}
inline void add(int u,int v){e[++cnt].v=v,e[cnt].next=first[u],first[u]=cnt,++du[v];}
inline bool bfs(int s){
    queue<int>q;
    q.push(s);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        in[x]=true;
        if(x>=1&&x<=m)ans[++tot]=x;
        for(int i=first[x];~i;i=e[i].next){
            int v=e[i].v;
            --du[v];
            if(!du[v])q.push(v);
        }
    }
    bool f=true;
    for(int i=1;i<=m;++i){
        if(!vis[i])ans[++tot]=i;
        else if(!in[i]){f=false;break;}
    }
    return f;
}
int main(){
//  freopen("table.in","r",stdin);
//  freopen("table.out","w",stdout);
    memset(first,-1,sizeof(first));
    int t,s=0;
    n=read(),t=m=read();
    for(int tt=1;tt<=n;++tt){
        ++t,add(s,t);
        for(int j=1;j<=m;++j)q[j].id=j,q[j].v=read();
        sort(q+1,q+m+1,cmp);
        int pos=1;
        while(q[pos].v==-1)++pos;
        hd=tl=pos;
        for(int j=pos;j<=m;++j)vis[q[j].id]=1;
        while(pos<=m){
            while(q[pos+1].v==q[pos].v&&pos<m)++pos,++tl;
            for(int i=hd;i<=tl;++i)add(t,q[i].id),add(q[i].id,t+1);
            ++t,hd=tl=++pos;
        }
    }
    bool f=bfs(s);
    if(!f){puts("-1");return 0;}
    for(int i=1;i<=m;++i)cout<<ans[i]<<' ';
    return 0;
}

巴特西