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