HDU - 1281 棋盘游戏（二分图匹配）

HDU - 1281 棋盘游戏

N * M 的矩阵上，规定几个方格可以放车，
求最多放几个车互不冲突，哪些车是import（这个点不放（最大放车数会减少））先用匈牙利算法求一下最大放车数量，再将每个点去掉，看看最大匹配会不会减少，由此判断一下是不是import点

#include<cstdio>
#include<cstring> 
const int N = 110;
int vis[N],pre[N],match[N][N];
int x[N*N],y[N*N];
int n,m,k;int dfs(int x)
{
    for(int i=1;i<=m;i++)//宽 {
    if(!vis[i]&&match[x][i]){
    vis[i]=1;if(pre[i]==-1||dfs(pre[i])){
    pre[i]=x;return 1;}}}return 0;
}int Maxmatch()
{
    memset(pre,-1,sizeof pre);int ans=0;for(int i=1;i<=n;i++)//高 {
    memset(vis,0,sizeof vis);ans+=dfs(i);}return ans;
} int main()
{
    int t=1;while(scanf("%d%d%d",&n,&m,&k)!=EOF){
    memset(match,0,sizeof match);for(int i=1;i<=k;i++){
    scanf("%d%d",&x[i],&y[i]);match[x[i]][y[i]]=1;}int ans=Maxmatch();int res=0;for(int i=1;i<=k;i++){
    match[x[i]][y[i]]=0;int sum=Maxmatch();if(sum<ans) res++;match[x[i]][y[i]]=1;}printf("Board %d have %d important blanks for %d chessmen.\n",t++,res,ans);}return 0;
}