CF 274 D Lovely Matrixトポロジー並べ替え、縮み難易度:2

2796 ワード

http://codeforces.com/problemset/problem/274/D
この問題の解題の構想:
各行の統計については、小値列を弧尾、大値列を弧頭、(-1を除く、弧を結ばない)として、得る図をトポロジーソートすればよい.
しかし、本題のデータは大きいので、縮点を行う必要があります.同じ数値の点を縮めて、新しい大きな点になります.元の小さな値列は大きな点に接続され、大きな点から大きな値列に接続され、辺数を減らすことができます.
例えば、本来の取値が1のものは4点、取値が2のものは5点、
縮まないで、20本の辺が必要です.
縮小点、4+1+5=10エッジのみ
△でも、私はやはりこの方法がちょっと投機的だと思います.
#include <cstdio>

#include <algorithm>

#include <vector>

#include <queue>

using namespace std;

const int maxn=2e5+3;

typedef pair<int,int> P;

P a[maxn];

int deg[maxn];

bool used[maxn];

int ans[maxn];

vector <int >e[maxn];

queue<int> que;

int n,m,last,flast;



int main(){

        scanf("%d%d",&n,&m);

        flast=m+1;

        for(int i=0;i<n;i++){

                for(int j=0;j<m;j++){

                        scanf("%d",&a[j].first);

                        a[j].second=j+1;

                }

                sort(a,a+m);



                last=flast;

                for(int j=0;j<m;){

                        if(a[j].first==-1){j++;continue;}

                        int k=j;

                        while(a[k].first==a[j].first){

                                e[a[k].second].push_back(last);

                                deg[last]++;

                                if(last>flast){

                                        e[last-1].push_back(a[k].second);

                                        deg[a[k].second]++;

                                }

                                k++;

                        }

                        last++;

                        j=k;

                }

                flast=last;

        }

        for(int i=1;i<=m;i++){

               if(deg[i]==0){

                        que.push(i);

               }

        }

        int len=0;

        while(!que.empty()&&len<m){

                int s=que.front();que.pop();

                if(used[s])continue;

                used[s]=true;

                if(s<=m)ans[len++]=s;

                for(int i=0;i<e[s].size();i++){

                        int t=e[s][i];

                        if(!used[t]){

                                deg[t]--;

                                if(deg[t]==0){

                                        que.push(t);

                                }

                        }

                }

        }

        if(len<m){

                puts("-1");

        }

        else for(int i=0;i<len;i++){

                printf("%d%c",ans[i],i==len-1?'
':' '); } return 0; }