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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

SGU322 dfs+动态维护边表  

2012-08-13 21:15:55|  分类: SGU300系列 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
其实该题本意应该是要人动态维护邻接表的
在我的邻接矩阵华丽丽得超时后,怒开set暴力水过了

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

const int NUM=2000+10;
const int MAX=16000+10;

int n;

int aa[MAX],ab[MAX],ac[MAX],ad[MAX],num;
int qx[MAX],qy[MAX];

set<int> g[MAX],t[MAX];

int dfs(int S,int T,int u,int fa)
{
if(u==T)return -1;
int v,temp,x,y;
set<int>::iterator it;
for(it=g[u].begin();it!=g[u].end();++it)
{
v=*it;
if(v==fa)continue;
temp=dfs(S,T,v,u);
if(!temp)continue;
if(temp==1)return 1;

x=u;y=v;
if(t[x].find(y)==t[x].end())
{
++num;
aa[num]=S,ab[num]=T,ac[num]=x,ad[num]=y;
g[x].erase(y);
g[y].erase(x);
g[S].insert(T);
g[T].insert(S);
return 1;
}else return -1;
}
return 0;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
int i,x,y;
scanf("%d ",&n);
for(i=1;i<n;++i)
{
scanf("%d %d",&x,&y);
qx[i]=x;qy[i]=y;
t[x].insert(y);
t[y].insert(x);
}
for(i=1;i<n;++i)
{
scanf("%d %d",&x,&y);
g[x].insert(y);
g[y].insert(x);
}
for(i=1;i<n;++i)
if(g[qx[i]].find(qy[i])==g[qx[i]].end())
dfs(qx[i],qy[i],qx[i],0);
printf("%d\n",num);
for(i=1;i<=num;++i)
printf("2 %d %d %d %d\n",aa[i],ab[i],ac[i],ad[i]);
}




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

历史上的今天

评论

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

页脚

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