CH6802 車的放置

描述

给定一个N行M列的棋盘,已知某些格子禁止放置。问棋盘上最多能放多少个不能互相攻击的車。車放在格子里,攻击范围与中国象棋的“車”一致。N,M≤200。

输入格式

第一行为n,m,t(表示有t个禁止的格子)
第二行到t+1行为x,y,分别表示禁止格子所在的位置,x为第x行,y为第y列,行列编号从1开始。 

输出格式

一个整数,表示最多能放多少个車。

样例输入

8 8 0

样例输出

8

题解

把行、列看成节点
1要素:行节点、列节点只能放一个
0要素:行节点之间没有边,列节点之间也没有
所以建二分图跑最大匹配,时间复杂度\(O((n+m)nm)\)

#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;rg char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-') w=-w;
    for(;isdigit(ch);ch=getchar()) data=data*10+ch-'0';
    return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;

co int N=201;
int n,m,t,ans,fa[N];
bool a[N][N],v[N];
bool dfs(int x){
    for(int y=1;y<=m;++y){
        if(a[x][y]||v[y]) continue;
        v[y]=1;
        if(!fa[y]||dfs(fa[y])){
            fa[y]=x;
            return 1;
        }
    }
    return 0;
}
int main(){
    read(n),read(m),read(t);
    while(t--) a[read<int>()][read<int>()]=1;
    for(int i=1;i<=n;++i){
        memset(v,0,sizeof v);
        ans+=dfs(i);
    }
    printf("%d\n",ans);
    return 0;
}
上一篇:《字符串专题》


下一篇:【luogu2293】【bzoj1213】 [HNOI2004]高精度开根 [高精度]