373. 車的放置
作者:
b507jiang
,
2021-06-20 21:27:29
,
所有人可见
,
阅读 269
#include <bits/stdc++.h>
using namespace std;
const int N=205, M=N*2;
int ver[M],nxt[M],head[N*2],tot=1;
int n,m,t,ans;
bool ban[N][N],v[N*2];
int match[N*2];
void add(int x,int y){
ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}
bool dfs(int x){
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(v[y])continue;
v[y]=true;
if(!match[y] || dfs(match[y])) {
match[y]=x;
return true;
}
}
return false;
}
int main(){
cin>>n>>m>>t;
for(int i=1;i<=t;i++){
int x,y;
scanf("%d%d",&x,&y);
ban[x][y]=true;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if( ban[i][j] ) continue;
add(i,n+j);
}
for(int i=1;i<=n;i++){
memset(v,0,sizeof v);
if( dfs(i) ) ans++;
}
cout<<ans<<endl;
}
江老师好