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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

ural1099 任意图匹配 带花树  

2012-08-28 17:07:09|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
照着范爷的程序一点一点改,于是便AC了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using std::vector;
using std::queue;

const int MAX=222+10;

int n,g[MAX][MAX];
vector<int> E[MAX];

int next[MAX],hash[MAX],mark[MAX],fa[MAX],link[MAX],hash_count;
queue<int> q;

int findfather(int u)
{
return (fa[u]==u)?u:(fa[u]=findfather(fa[u]));
}

void merge(int x,int y)
{
int a=findfather(x),b=findfather(y);
if(a!=b)
fa[a]=b;
}

int findLCA(int u,int v)
{
++hash_count;
while(u)
{
hash[u=findfather(u)]=hash_count;
u=next[link[u]];
}
while(v)
{
if(hash[v=findfather(v)]==hash_count)return v;
v=next[link[v]];
}
return 0;
}

void shrink(int a,int p)
{
int b,c;
while(a!=p)
{
b=link[a];c=next[b];
if(findfather(c)!=p)next[c]=b;
if(mark[b]==2)q.push(b),mark[b]=1;
if(mark[c]==2)q.push(c),mark[b]=1;
merge(a,b);merge(b,c);
a=c;
}
}

void unit(int u,int v)
{
int p=findLCA(u,v);
if(findfather(u)!=p)
next[u]=v;
if(findfather(v)!=p)
next[v]=u;
shrink(u,p);
shrink(v,p);
}

void Augment(int u)
{
int t,v;
for(;u;)
{
v=next[u];
t=link[v];
link[u]=v;
link[v]=u;
u=t;
}
}

void insert(int a,int b)
{
int c=link[b];
next[b]=a;
mark[b]=2;mark[c]=1;
q.push(c);
}

void findAugment(int S)
{
int i,u,v,flag=0;

for(hash_count=0,i=1;i<=n;++i)
{
hash[i]=mark[i]=next[i]=0;
fa[i]=i;
}
while(!q.empty())q.pop();
for(q.push(S),mark[S]=1;!q.empty() && !flag;)
{
u=q.front();q.pop();
for(i=0;i<(int)E[u].size();++i)
{
v=E[u][i];
if(mark[u]!=2 && findfather(u)!=findfather(v) && v!=link[u])
{
if(!link[v])
{
next[v]=u;
Augment(v);
flag=1;
break;
}
else if(mark[v]==1)
unit(u,v);
else if(mark[v]==0)
insert(u,v);
}
}
}
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
int a,b,i;
scanf("%d ",&n);
while(scanf("%d %d",&a,&b)!=EOF)
{
if(a==b)continue;
if(g[a][b])continue;
g[a][b]=g[b][a]=1;
E[a].push_back(b);
E[b].push_back(a);
}
for(i=1;i<=n;++i)
if(!link[i])
findAugment(i);
int ans=0;
for(i=1;i<=n;++i)
if(link[i])++ans;
printf("%d\n",ans);
for(i=1;i<=n;++i)
if(link[i] && link[i]>i)
printf("%d %d\n",i,link[i]);
return 0;
}




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

历史上的今天

评论

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

页脚

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