首页 > 代码库 > hdu 1281 二分图最大匹配

hdu 1281 二分图最大匹配

2024-08-28 19:58:51   210人阅读

对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 101bool 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);    }}

 

hdu 1281 二分图最大匹配


联系
我们