hdu 1281 二分图最大匹配

对N个可以放棋子的点(X1,Y1),(x2,Y2)......(Xn,Yn);我们把它竖着排看看~（当然X1可以对多个点~）

X1 Y1

X2 Y2

X3 Y3

.....

Xn Yn

可以发现：可以根据X坐标与Y坐标把这些点转换为二分图！

首先：只有左边的点与右边的点有关系

其次：符合二分图的最大匹配特性，可以看到如果选择了（X1，Y1）这个点，那么X1与Y1都不能与其他点匹配了，不然的话棋子会互相攻击！

最后：找关键点，只要枚举每条边，删了，看看最大匹配有没有减小，减小了就是关键点（边）了

#include<iostream>

using namespace std;

#define N 101

bool map[N][N];

int pre[N];

bool h[N];

struct node{

    int u,v;

}p[N*N];

int n,m,k;

void init(){

    memset(map,,sizeof(map));

    memset(pre,-,sizeof(pre));

}

bool dfs(int u){

    for(int v=;v<=m;v++)

        if(map[u][v]&&!h[v]){

            h[v]=;

            if(pre[v]==-||dfs(pre[v])){

                pre[v]=u;

                return true;

            }

        }

    return false;

}

int main(void){

    int index=;

    while(~scanf("%d%d%d",&n,&m,&k)){

        init();

        for(int i=;i<k;i++){

            scanf("%d%d",&p[i].u,&p[i].v);

            map[p[i].u][p[i].v]=;

        }

        int _max=,ans=;

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

            memset(h,,sizeof(h));

            if(dfs(i))

                _max++;

        }

        for(int i=;i<k;i++){

            int count=;

            map[p[i].u][p[i].v]=;

            memset(pre,-,sizeof(pre));

            for(int j=;j<=n;j++){

                memset(h,,sizeof(h));

                if(dfs(j))

                    count++;

            }

            if(count!=_max)

                ans++;

            map[p[i].u][p[i].v]=;

        }

        printf("Board %d have %d important blanks for %d chessmen.\n",index++,ans,_max);

    }

}

巴特西

hdu 1281 二分图最大匹配

最新文章

热门文章