【CH6802】车的放置
2024-08-28 20:59:19
题目大意:给定一个 N*M 的棋盘,棋盘上有些点不能放置任何东西,现在在棋盘上放置一些车,问最多可以放置多少个车而不会互相攻击。
题解:将放置一个车看作连接一条无向边,因为每一行和每一列之间只能放置一个车,即:车的位置在 (i,j) 时,表示第 i 行和第 j 列之间放置了一个车。可以发现,一个车不会影响到其他的行和列,因此所有的行和所有列之间是没有连边的,这符合二分图的性质。根据建模,跑匈牙利算法即可,时间复杂度为 \(O((N+M)*N*M)\)。
代码如下
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
const int maxn=401;
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll sqr(ll x){return x*x;}
inline ll read(){
ll x=0,f=1;char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));
do{x=x*10+ch-'0';ch=getchar();}while(isdigit(ch));
return f*x;
}
/*--------------------------------------------------------*/
vector<int> G[maxn];
int match[maxn];bool vis[maxn];
int n,m,t,mpp[201][201];
int ans;
void read_and_parse(){
n=read(),m=read(),t=read();
for(int i=1;i<=t;i++)mpp[read()][read()]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(!mpp[i][j])
G[i].pb(j+n),G[j+n].pb(i);
}
bool dfs(int u){
for(auto v:G[u])if(!vis[v]){
vis[v]=1;
if(!match[v]||dfs(match[v])){
match[v]=u;return 1;
}
}
return 0;
}
void solve(){
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(dfs(i))++ans;
}
printf("%d\n",ans);
}
int main(){
read_and_parse();
solve();
return 0;
}
最新文章
- DayPilot 7.8 DLL去DEMO字样下载
- Django分析之国际化处理
- Nginx-->;基础-->;安装-->;001:安装总结
- isee - 创建项目 - 1
- Oracle如何写出高效的SQL
- [HDOJ5952]Counting Cliques(DFS,剪枝)
- 再造轮子之网易彩票-第一季(IOS 篇 by sixleaves)
- 大数据系列修炼-Scala课程06
- 禁止将http请求强制转换为https请求
- 根据PV统计出前三的热门板块,并统计出热门板块下的用户数--方式一
- Java Web项目(Extjs)报错四
- Linux下使用Nginx端口转发出现502错误的一种解决办法
- NancyFX 第三章 Web框架
- UVA10570-Meeting with Aliens(枚举)
- MT【268】投篮第一次很重要
- 贝叶斯网络与LDA
- PHP开发——常量
- idea中的常用快捷键
- 51nod 1057 N的阶乘 (大数运算)
- python--表达式(运算表达式)
热门文章
- day 7-5 守护线程
- 本地数据访问时出现跨域问题Cross origin requests are only supported for protocol schemes: ……
- 用户认证--------------auth模块
- kibana——es的批量操作
- How to proof RSA
- hdu 5652(并查集)
- Nginx grpc反向代理
- MySQL的my.cnf文件(解决5.7.18下没有my-default.cnf)
- Spring MVC 使用介绍(二)—— DispatcherServlet
- python 文件下载