hdu 1281 二分图最大匹配

落日映苍穹つ 2022-03-30 07:38 399阅读 0赞

对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,0,sizeof(map));
        memset(pre,-1,sizeof(pre));
    }
    bool dfs(int u){
        for(int v=1;v<=m;v++)
            if(map[u][v]&&!h[v]){
                h[v]=1;
                if(pre[v]==-1||dfs(pre[v])){
                    pre[v]=u;
                    return true;
                }
            }
        return false;
    }
    int main(void){
        int index=1;
        while(~scanf("%d%d%d",&n,&m,&k)){
            init();
            for(int i=0;i<k;i++){
                scanf("%d%d",&p[i].u,&p[i].v);
                map[p[i].u][p[i].v]=1;
            }
            int _max=0,ans=0;
            for(int i=1;i<=n;i++){
                memset(h,0,sizeof(h));
                if(dfs(i))
                    _max++;
            }
            for(int i=0;i<k;i++){
                int count=0;
                map[p[i].u][p[i].v]=0;
                memset(pre,-1,sizeof(pre));
                for(int j=1;j<=n;j++){
                    memset(h,0,sizeof(h));
                    if(dfs(j))
                        count++;
                }
                if(count!=_max)
                    ans++;
                map[p[i].u][p[i].v]=1;
            }
            printf("Board %d have %d important blanks for %d chessmen.\n",index++,ans,_max);
        }
    }