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

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2184]任意图的匹配  

2015-06-02 21:15:48|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2184: 任意图的匹配

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 36  Solved: 12
[Submit][Status][Discuss]

Description

每天都要考,每天都要讲,大家注意力都集中不起来了,每天听解题报告时都有人交头接耳(也包括我,呵呵)。这样做大大的影响的学习效率(可能吧)。于是,有些好奇心重的同学就开始研究,怎样才会最吵。培训的总共有N个人,但不是每两人之间都讲话,只有一些人有话题聊,而且一个人可能会和多个人有话题(共M对人)。如果所有同学都说在话,教室里最吵。你的任务就是求出把说话者对数控制在多少人以内,无论如何教室里不会变得最吵?注意:A和B说话,同时B和C说话,这算两对人说话。

Input

第一行两个整数N,M。接下来M行,每行两个整数x,y表示x和y有话题聊。

Output

一行,一个整数表示要把说话者对数控制在多少以内,无论如何教室里不最吵。

Sample Input

5 5 1 3 2 3 1 4 2 4 1 5

Sample Output

2 约定:N<=1000,M<=3000。 有多组数据,做到文件底结束

Solution

关键在于对奇环的处理。带花树采取了缩环,将原来奇环上的每一个奇点都置为偶点,然后再次进行增广。
下面是一份有注释的我的带花树
#include<cstdio>
#include<cstring>
#define N 510
char ch,B[1<<15],*S=B,*T=B;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
int aa;int F(){
while(ch=getc(),ch<'0'||ch>'9');aa=ch-48;
while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-48;return aa;
}
int n,m,x,y,i,la[N],et,mate[N],fa[N],ans,pre[N],sta[N],vis[N],tim,z,q[N],l,r;
//et,la[],e[]记录边表
//fa[],gf()表示并查集
//mate[]表示当前与这个点匹配的另一个点是谁,如果该点未被匹配则值为0
//ans表示当前匹配边的条数
//pre[]表示在当前match()的时候交错边的father
//sta[]表示一个节点的状态,-1表示未被访问,0表示为偶点,1表示为奇点
//vis[],tim用于寻找lca,打时间戳
//切记偶点到奇点为交错边,奇点到偶点为匹配边,都是单向边
struct E{int to,nxt;}e[333333];
#define add(x,y) (e[++et]=(E){y,la[x]},la[x]=et)
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
int lca(int x,int y){
for(++tim,x=gf(x),y=gf(y);;z=x,x=y,y=z)if(x){
if(vis[x]==tim)return x;//如果当前点已被访问则为lca
vis[x]=tim,x=mate[x]?gf(pre[mate[x]]):0;//否则标记当前点已被访问,将该节点向上跳一次匹配边和交错边
}
}
int blossom(int x,int y,int g){//g表示花根
while(gf(x)!=g){
pre[x]=y;//原来有pre[y]=x,加了pre[x]=y以后在花上就变成了一个双向边,而花是奇花,顺时针绕和逆时针绕只有一种是可增广的
if(sta[mate[x]]==1)sta[q[++r]=mate[x]]=0;//将原来的奇点置为偶点并加入队列中更新
if(gf(x)==x)fa[x]=g;if(gf(mate[x])==mate[x])fa[mate[x]]=g;//更新花
y=mate[x],x=pre[y];//向上跳
}
}
int match(int s){
memset(sta,-1,sizeof(sta));
memset(pre,0,sizeof(pre));int i,j,las;
for(i=1;i<=n;i++)fa[i]=i;//初始化
for(q[l=r=0]=s,sta[s]=0;l<=r;l++)//第一个点为偶点,队列里面只存偶点
for(i=la[q[l]];i;i=e[i].nxt)
if(sta[e[i].to]==-1){
sta[e[i].to]=1,pre[e[i].to]=q[l];//如果当前节点未被访问,则标记为奇点
if(!mate[e[i].to]){//如果该奇点没有匹配边,则找到增广路径
for(j=q[l],i=e[i].to;j;j=pre[i=las])las=mate[j],mate[j]=i,mate[i]=j;//将匹配边和交错边对掉
return 1;
}
sta[q[++r]=mate[e[i].to]]=0;//如果该奇点有匹配边,则将与其匹配的那个偶点扔进队列更新
}
else if(fa[e[i].to]!=fa[q[l]]&&sta[e[i].to]==0)//如果当前边不在一朵花中,并且这条边连接的是两个偶点
j=lca(e[i].to,q[l]),blossom(e[i].to,q[l],j),blossom(q[l],e[i].to,j);//找到花根,然后缩花
//否则什么事都不用做,因为不影响答案,比如奇点-边-偶点,等等
return 0;
}
int main(){
for(n=F(),m=F(),i=1;i<=m;i++)
if(x=F(),y=F(),add(x,y),add(y,x),!mate[x]&&!mate[y])mate[x]=y,mate[y]=x,ans++;
//如果在开始的时候,能匹配就匹配,这并不影响最终结果,有可能提升一些程序的运行效率
for(i=1;i<=n;i++)if(!mate[i]&&match(i))ans++;
for(printf("%d\n",ans),i=1;i<=n;i++)printf("%d ",mate[i]);puts("");
}

Code

/**************************************************************
    Problem: 2184
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:40 ms
    Memory:912 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
char ch,B[1<<15],*S=B,*T=B;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
int aa;int F(){
    while(ch=getc(),ch<'0'||ch>'9')if(ch<=0)return 0;aa=ch-48;
    while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-48;return aa;
}
#define N 1010
int n,m,x,y,v,mate[N],fa[N],pre[N],la[N],et,ans,q[N],l,r,sta[N],vis[N],tim;
struct E{int to,nxt;}e[6010];
#define add(x,y) (e[++et]=(E){y,la[x]},la[x]=et)
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
int lca(int x,int y){
    for(++tim,x=gf(x),y=gf(y);;v=x,x=y,y=v)if(x){
        if(vis[x]==tim)return x;
        vis[x]=tim,x=gf(pre[mate[x]]);
    }
}
int blossom(int x,int y,int g){
    while(gf(x)!=g){
        if(pre[x]=y,sta[mate[x]]==1)sta[q[++r]=mate[x]]=0;
        if(gf(x)==x)fa[x]=g;if(gf(mate[x])==mate[x])fa[mate[x]]=g;
        y=mate[x],x=pre[y];
    }
}
int match(int s){int i,j,las;
    memset(pre,0,sizeof(pre));
    memset(sta,-1,sizeof(sta));
    for(i=1;i<=n;i++)fa[i]=i;
    for(q[l=r=0]=s,sta[s]=0;l<=r;l++)
    for(i=la[q[l]];i;i=e[i].nxt)
    if(sta[e[i].to]==-1){
        pre[e[i].to]=q[l],sta[e[i].to]=1;
        if(!mate[e[i].to]){
            for(j=q[l],i=e[i].to;j;j=pre[i=las])las=mate[j],mate[j]=i,mate[i]=j;
            return 1;
        }
        sta[q[++r]=mate[e[i].to]]=0;
    }
    else if(gf(e[i].to)!=gf(q[l])&&sta[e[i].to]==0)
        j=lca(e[i].to,q[l]),blossom(e[i].to,q[l],j),blossom(q[l],e[i].to,j);
    return 0;
}
int main(){
    while(n=F()){
        memset(la,0,sizeof(la)),et=ans=0;
        memset(mate,0,sizeof(mate));
        for(m=F();m--;x=F(),y=F(),add(x,y),add(y,x),!mate[x]&&!mate[y]?ans++,mate[x]=y,mate[y]=x:1);
        for(int i=1;i<=n;i++)if(!mate[i]&&match(i))ans++;
        printf("%d\n",n-ans-1);
    }
}
  评论这张
 
阅读(135)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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