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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

IOI 国家队训练3 problem 平面图O(n)判定  

2012-09-24 19:18:08|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
两天的时间啊
除了玩游戏王和看某些不和谐内容外,都是一心一意的使劲想。
以后有时间写个题解吧
真心是我所见过的最难的算法了
任重而道远啊
先只贴代码了,比古楠的短了不少,代价是将O(n)变成了O(nlogn)

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<iostream>
#define mp make_pair
#define pb push_back
using std::vector;
using std::set;
using std::swap;
using std::min;
using std::max;
using std::pair;
using std::make_pair;

const int MAX=400+10;

int n,m,hash[MAX],que[MAX],fa[MAX],deep[MAX],low[MAX],ecp[MAX];
vector<int> link[MAX],son[MAX];
set< pair<int,int> > SDlist[MAX],proots[MAX];
int next[MAX][2],back[MAX],rev[MAX];

void dfs(int u)
{
hash[u]=1;
que[++que[0]]=u;
ecp[u]=low[u]=deep[u];
int i,v;
for(i=0;i<(int)link[u].size();++i)
{
if(!hash[v=link[u][i]])
{
fa[v]=u;
deep[v]=deep[u]+1;
dfs(v);
low[u]=min(low[u],low[v]);
SDlist[u].insert(mp(low[v],v));
}
else ecp[u]=min(ecp[u],deep[v]);
}
low[u]=min(low[u],ecp[u]);
return;
}

int visited[MAX];

void addtree(int u,int t1,int v,int t2)
{
next[u][t1]=v;
next[v][t2]=u;
}

void findnext(int u,int v,int& u1,int& v1)
{
u1=next[u][v^1];
if(next[u1][0]==u)
v1=0;
else v1=1;
}

void walkup(int u,int v)
{
back[v]=u;
int v1=v,v2=v,u1=1,u2=0,z;
while(1)
{
if(hash[v1]==u || hash[v2]==u)
break;
hash[v1]=u;hash[v2]=u;
z=max(v1,v2);
if(z>n)
{
int p=fa[z-n];
if(p!=u)
{
// printf("%d %d\n",p,u);
proots[p].insert( make_pair( -low[z-n],z) );
v1=p,v2=p,u1=0,u2=1;
}
else break;
}
else
{
findnext(v1,u1,v1,u1);
findnext(v2,u2,v2,u2);
}
}
}

int topstack;
pair<int,int> stack[MAX];

int outer(int u,int v)
{
return ecp[v]<deep[u] || (SDlist[v].size() && SDlist[v].begin()->first<deep[u]);
}

int inside(int u,int v)
{
return proots[v].size()>0 || back[v]==u;
}

int active(int u,int v)
{
return inside(u,v) || outer(u,v);
}

void push(int a,int b)
{
stack[++topstack]=mp(a,b);
}

void mergestack()
{
int v1,t1,v2,t2,s,s1;
v1=stack[topstack].first;t1=stack[topstack].second;
topstack--;
v2=stack[topstack].first;t2=stack[topstack].second;
topstack--;

s=next[v1][t1^1];
s1=(next[s][1]==v1);
next[s][s1]=v2;
next[v2][t2]=s;

SDlist[v2].erase( make_pair(low[v1-n],v1-n) );
proots[v2].erase( make_pair(-low[v1-n],v1) );
}

void findnextActive(int u,int t,int& v,int& w1,int S)
{
findnext(u,t,v,w1);
while(u!=v && !active(S,v))
{
findnext(v,w1,v,w1);
}
}

void walkdown(int S,int u)
{
topstack=0;
int t1,v=S,w1,x2,y2,x1,y1,p;
for(t1=0;t1<2;++t1)
{
findnext(S,t1^1,v,w1);
while(v!=S)
{
if(back[v]==u)
{
while(topstack>0)
{
mergestack();
}
addtree(S,t1,v,w1);
back[v]=0;
}
if(proots[v].size())
{
push(v,w1);

p=proots[v].begin()->second;
findnextActive(p,1,x1,y1,u);
findnextActive(p,0,x2,y2,u);
if(active(u,x1) && !outer(u,x1))
v=x1,w1=y1;
else if(active(u,x2) && !outer(u,x2))
v=x2,w1=y2;
else if(inside(u,x1) || back[x1]==u)
v=x1,w1=y1;
else v=x2,w1=y2;

push(p,v==x2);
}
else
{
if(v>n || ( ecp[v]>=deep[u] && !outer(u,v) ))
{
findnext(v,w1,v,w1);
}
else
{
if(v<=n && outer(u,v) && !topstack)
{
addtree(S,t1,v,w1);
}
break;
}
}
}
}
}

int work(int u)
{
if(0 && u==que[9])
{
int i;

for(i=1;i<=2*n;++i)
if(next[i][0])
{
printf("%d %d %d\n",i,next[i][0],next[i][1]);
}
for(i=1;i<=n;++i)
printf("%d\n",SDlist[i].size());
}
int i,v;
for(i=0;i<(int)link[u].size();++i)
if(fa[v=link[u][i]]==u)
{
son[u].push_back(n+v);
proots[n+v].clear();
addtree(n+v,1,v,0);
addtree(n+v,0,v,1);
}
for(i=0;i<(int)link[u].size();++i)
if(deep[v=link[u][i]]>deep[u]+1)
{
walkup(u,v);
}
topstack=0;
for(i=0;i<(int)son[u].size();++i)
{
walkdown(son[u][i],u);
}
for(i=0;i<(int)link[u].size();++i)
if(deep[v=link[u][i]]>deep[u]+1 && back[v])
{
return 0;
}
return 1;
}

int main()
{
/*
#ifndef ONLINE_JUDGE
freopen("input10.txt","r",stdin);
freopen("output10.txt","w",stdout);
#endif
*/
while(scanf("%d",&n)!=EOF)
{
int i,a,b,flag=1;
scanf("%d",&m);
for(i=1;i<=2*n;++i)
{
link[i].clear();
SDlist[i].clear();
son[i].clear();
proots[i].clear();
next[i][0]=next[i][1]=0;
fa[i]=0;
hash[i]=0;low[i]=ecp[i]=deep[i]=back[i]=0;
que[0]=0;
}
for(i=1;i<=m;++i)
{
scanf("%d %d",&a,&b);
link[a].push_back(b);
link[b].push_back(a);
}
if(m>3*n-5)
{
printf("NO\n");
continue;
}
memset(hash,0,sizeof hash);
for(i=1;i<=n;++i)
if(!hash[i])
{
deep[i]=1;
dfs(i);
}
memset(hash,0,sizeof hash);
for(i=n;i>=1;--i)
{
if(!work(que[i]))
{
flag=0;
break;
}
}
if(!flag)
printf("NO\n");
else printf("YES\n");
}
}



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

历史上的今天

评论

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

页脚

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