POJ3715【二分匹配-增广】

题意：

N个人，有两种人，M对亲密关系，问最少删除几个人达到没有亲密关系。

思路：

最大匹配 = 最小独立集，删掉该人对最大匹配数的影响，如果没有影响，删不删都无所谓，如果有影响贼删除；

类似HDU1281；

处理可用删除这个点以后找增广，如果找的到增广则无影响，找不到增广则有影响。

错误就是二分图，我要删的点有两种，两组点都有可能删除，*单方面删除了一种*。

错误在了无意识偏爱了一张图，其实二分图，两张图非常独立，地位平等且重要！

//#include<bits/stdc++.h>

//using namespace::std;

//typedef pair<int,int> PII;

#include<cstdio>

#include<iostream>

#include<string.h>

#include<algorithm>

using namespace std;

const int N=2e2+10;

bool ma[N][N];

int cx[N],cy[N],n,m;

bool vis[N],col[N],deleted[N];

bool FindPateX(int u)

{

    if(deleted[u]) return false;

    for(int i=0;i<n;i++)

    {

        if(ma[u][i]&&!vis[i]&&!deleted[i]&&col[i])

        {

            vis[i]=true;

            if(cy[i]==-1||FindPateX(cy[i]))

            {

                cx[u]=i;

                cy[i]=u;

                return true;

            }

        }

    }

    return false;

}

bool FindPateY(int u)

{

    if(deleted[u]) return false;

    for(int i=0;i<n;i++)

    {

        if(ma[u][i]&&!vis[i]&&!deleted[i]&&!col[i])

        {

            vis[i]=true;

            if(cx[i]==-1||FindPateY(cx[i]))

            {

                cx[i]=u;

                cy[u]=i;

                return true;

            }

        }

    }

    return false;

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int u,v;

        scanf("%d%d",&n,&m);

        for(int i=0;i<n;i++) scanf("%d",&col[i]);

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

        while(m--)

        {

            scanf("%d%d",&u,&v);

            if(col[u]!=col[v])

                ma[u][v]=ma[v][u]=1;

        }

        int ans=0;

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

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

        memset(deleted,false,sizeof(deleted));

        for(int i=0;i<n;i++)

        {

            if(!col[i]&&cx[i]==-1)

            {

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

                ans+=FindPateX(i);

            }

        }

        printf("%d",ans);

        int temp;

        for(int i=0;i<n;i++)

        {

            if(!col[i])

            {

                if(cx[i]!=-1)

                {

                    temp=cx[i];

                    cx[i]=cy[temp]=-1;

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

                    deleted[i]=true;

                    if(FindPateY(temp))

                        deleted[i]=false;

                    else

                        printf(" %d",i);

                }

            }

            else

            {

                if(cy[i]!=-1)

                {

                    temp=cy[i];

                    cx[temp]=cy[i]=-1;

                    deleted[i]=true;

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

                    if(FindPateX(temp))

                        deleted[i]=false;

                    else

                        printf(" %d",i);

                }

            }

        }

        puts("");

    }

    return 0;

}

巴特西

POJ3715【二分匹配-增广】

最新文章

热门文章