注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

SGU354 极好的题目——拓扑排序  

2012-08-26 13:04:54|  分类: SGU300系列 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
想了好久也没想出个所以然,然后到网上一查,才发现这是个top排序
然后算法就简单了,处理出每行每列之间的大小关系,然后通过这些关系建图,top排序得到答案
难点在如何n^2logn处理处每行每列的大小关系
我先是偷懒敲了Splay,然后TLE了
于是只得写Treap了,以后平衡树能用Treap还是用Treap!

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<ctime>
using namespace std;

const int MAX=700+10;

int n,lf[MAX][MAX],up[MAX][MAX];

struct Treap
{
struct node
{
int w,size,ch[2],p;
}tree[MAX];
int root;

void update(int u)
{
tree[u].size=tree[tree[u].ch[0]].size+tree[tree[u].ch[1]].size+1;
}

void rotate(int u)
{
int fa=tree[u].p,gfa=tree[fa].p;
int T=tree[fa].ch[1]==u,H=T^1;

tree[fa].ch[T]=tree[u].ch[H];
tree[tree[u].ch[H]].p=fa;

tree[u].ch[H]=fa;
tree[fa].p=u;

if(tree[gfa].ch[1]==fa)tree[gfa].ch[1]=u;
else tree[gfa].ch[0]=u;
tree[u].p=gfa;
if(!gfa)root=u;

update(fa);update(u);
}

void down(int u)
{
int m=u;
if(tree[u].ch[0] && tree[tree[u].ch[0]].w<tree[m].w)
m=tree[u].ch[0];
if(tree[u].ch[1] && tree[tree[u].ch[1]].w<tree[m].w)
m=tree[u].ch[1];
if(m==u)return;
rotate(m);
down(u);
}

void up(int u)
{
while(tree[u].p && tree[u].w<tree[tree[u].p].w)
rotate(u);
}

void path_update(int u)
{
for(;u;u=tree[u].p)update(u);
}

void insert(int u,int kth)
{
tree[u].w=rand();tree[u].ch[0]=tree[u].ch[1]=tree[u].p=0;
tree[u].size=1;
if(!root)
{
root=u;
return;
}
if(kth==0)
{
tree[u].ch[1]=root;tree[root].p=u;
root=u;
down(u);
return;
}
int p=root,k=kth;
while(tree[tree[p].ch[0]].size+1!=k)
{
if(tree[tree[p].ch[0]].size>=k)p=tree[p].ch[0];
else
{
k-=tree[tree[p].ch[0]].size+1;
p=tree[p].ch[1];
}
}
if(!tree[p].ch[1])
{
tree[p].ch[1]=u;
tree[u].p=p;
}
else
{
p=tree[p].ch[1];
for(;tree[p].ch[0];p=tree[p].ch[0]);
tree[p].ch[0]=u;tree[u].p=p;
}
path_update(u);
up(u);
}

void print(vector<int>& ans,int u)
{
if(!u)return;
print(ans,tree[u].ch[0]);
ans.push_back(u);
print(ans,tree[u].ch[1]);
}
};

Treap tt;

vector<int> work(vector<int> a)
{
vector<int> ans;
tt.root=0;
int i;
for(i=0;i<n;++i)
tt.insert(i+1,a[i]);
tt.print(ans,tt.root);
return ans;
}

const int MAXN=MAX*MAX*3;
int begin[MAXN],next[MAXN],t[MAXN],tot,in[MAXN];
int q[MAXN],first,last;
int ans[MAX][MAX];

void addedge(int x,int y)
{
t[++tot]=y;
next[tot]=begin[x];
begin[x]=tot;
++in[y];
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
srand(time(0));
scanf("%d ",&n);
int i,j,k,u,v;
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
{
scanf("%d",&up[i][j]);
if(up[i][j]>=i)
{
printf("0\n");
return 0;
}
}
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
{
scanf("%d",&lf[i][j]);
if(lf[i][j]>=j)
{
printf("0\n");
return 0;
}
}
for(i=1;i<=n;++i)
{
vector<int> d,ans;
for(j=1;j<=n;++j)
d.push_back(lf[i][j]);
ans=work(d);
for(k=0;k<n-1;++k)
addedge((i-1)*n+ans[k],(i-1)*n+ans[k+1]);
}
for(j=1;j<=n;++j)
{
vector<int> d,ans;
for(i=1;i<=n;++i)
d.push_back(up[i][j]);
ans=work(d);
for(k=0;k<n-1;++k)
addedge((ans[k]-1)*n+j,(ans[k+1]-1)*n+j);
}
first=last=1;
for(i=1;i<=n*n;++i)
if(in[i]==0)
q[last++]=i;
while(first<last)
{
u=q[first++];
for(i=begin[u];i;i=next[i])
{
v=t[i];
--in[v];
if(!in[v])
q[last++]=v;
}
}
if(last<=n*n)
{
printf("0\n");
return 0;
}
for(i=1;i<=n*n;++i)
{
u=(q[i]-1)/n+1,v=(q[i]-1)%n+1;
ans[u][v]=n*n-i+1;
}
for(i=1;i<=n;++i,printf("\n"))
for(j=1;j<=n;++j)
printf("%d ",ans[i][j]);

}





  评论这张
 
阅读(329)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018