hdu 2444 交叉染色判断二分图+二分最大匹配

/*1A 31ms*/

#include<stdio.h>

#include<string.h>

#define N 300

int n;

struct node {

int u,v,next;

}bian[N*N*2];

int color[N],vis[N],link[N],visit[N],ma[N][N],f[N],head[N],yong;

void addedge(int u,int v) {

bian[yong].u=u;

bian[yong].v=v;

bian[yong].next=head[u];

head[u]=yong++;

}

void init() {//初始化

    memset(ma,0,sizeof(ma));

    memset(f,0,sizeof(f));

    memset(visit,0,sizeof(visit));

    memset(link,-1,sizeof(link));

    memset(color,0,sizeof(color));

    memset(vis,0,sizeof(vis));

    memset(head,-1,sizeof(head));

    yong=0;

}

int ff(int u) {//二分匹配

int i;

for(i=1;i<=n;i++)

    if(visit[i]==0&&ma[u][i]) {

        visit[i]=1;

        if(link[i]==-1||ff(link[i])) {

            link[i]=u;

            return 1;

        }

    }

    return 0;

}

int find(int u,int f) {//交叉染色判定

int i;

for(i=head[u];i!=-1;i=bian[i].next) {

    int v=bian[i].v;

    if(f)

       ma[u][v]=1;//建立邻接矩阵

    else

        ma[v][u]=1;

    if(!vis[v]) {

        color[v]=!color[u];

        vis[v]=1;

        find(v,f^1);

    }

    else

        if(color[v]==color[u])return 0;

}

return 1;

}

int main() {

    int m,i,a,b,ok;

    while(scanf("%d%d",&n,&m)!=EOF) {

            init();

        while(m--) {

            scanf("%d%d",&a,&b);

            addedge(a,b);

            addedge(b,a);

            f[a]=f[b]=1;//存在

        }

        ok=0;

    for(i=1;i<=n;i++)

        if(!vis[i]&&f[i]) {

            color[i]=1;

            vis[i]=1;

            if(find(i,1)==0)

                ok=1;

        }

        if(ok) {//是否存在不能交叉染色的

            printf("No\n");

            continue;

        }

      b=0;

for(i=1;i<=n;i++) {//二分最大匹配

    memset(visit,0,sizeof(visit));

    b+=ff(i);

}

printf("%d\n",b);

    }

return 0;

}
巴特西

hdu 2444 交叉染色判断二分图+二分最大匹配

最新文章

热门文章
