POJ 1466 Girls and Boys(二分图匹配)
2024-10-20 20:41:54
【题目链接】 http://poj.org/problem?id=1466
【题目大意】
给出一些人和他们所喜欢的人,两个人相互喜欢就能配成一对,
问最后没有配对的人的最少数量
【题解】
求最少数量,就是最多匹配的补集,因此做一遍二分图匹配即可。
【代码】
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int MAX_V=1000;
const int INF=0x3f3f3f3f;
int V,match[MAX_V];
vector<int> G[MAX_V];
bool used[MAX_V];
void add_edge(int u,int v){
G[u].push_back(v);
G[v].push_back(u);
}
bool dfs(int v){
used[v]=1;
for(int i=0;i<G[v].size();i++){
int u=G[v][i],w=match[u];
if(w<0||!used[w]&&dfs(w)){
match[v]=u;
match[u]=v;
return 1;
}
}return 0;
}
int bipartite_matching(){
int res=0;
memset(match,-1,sizeof(match));
for(int v=0;v<V;v++){
if(match[v]<0){
memset(used,0,sizeof(used));
if(dfs(v))res++;
}
}return res;
}
int N,x,k,y;
void init(){
V=N;
for(int i=0;i<V;i++)G[i].clear();
for(int i=0;i<N;i++){
scanf("%d: (%d)",&x,&k);
for(int i=0;i<k;i++){
scanf("%d",&y);
add_edge(x,y);
}
}
}
void solve(){
printf("%d\n",N-bipartite_matching());
}
int main(){
while(~scanf("%d",&N)){
init();
solve();
}return 0;
}
最新文章
- html标签思维导图
- (转载)李剑英的CSLight入门指南结合NGUI热更新
- Bootstrap学习笔记(一) 排版
- 在code.org上自己写一个flappy bird游戏
- bzoj 1500: [NOI2005]维修数列 splay
- mysql 优化点小结
- Android-4
- Jenkins 远程构建任务
- linux关闭触摸板
- 使用js主函数的原因是等文档加载完了才给里面的元素添加东西 如果不使用主函数则文档加载时候无法找到元素则不能成功给元素添加事件
- cpp 常量函数(函数后加const)
- 设计图与html 对比
- PageHelper分页插件
- cocos2dx spine之一 :spine缓存 (c++ &; lua)
- [转]如何远程连接运行OpenGL/Cuda 等GPU程序
- MFCC
- 第82讲:Scala中List的ListBuffer是如何实现高效的遍历计算的?
- Downloading files from a server to client, using ASP.Net, when file size is too big for MemoryStream using Generic Handlers (ashx)
- Mysql Innodb 性能参数设置 https://www.rathishkumar.in/2017/01/how-to-allocate-innodb-buffer-pool-size-in-mysql.html
- 安装Hadoop系列 — 安装SSH免密码登录
热门文章
- [hdu 3652]数位dp解决数的倍数问题
- bzoj 4880 [Lydsy1705月赛]排名的战争 贪心
- Kafka自我学习-报错篇
- Python爬虫学习笔记之爬取新浪微博
- Cannot read property &#39;resetFields&#39; of undefined 问题及引申
- sql注入预防
- 12.22笔记(关于CALayer//Attributes//CALayer绘制图层//CALayer代理绘图//CALayer动画属性//CALayer自定义子图层//绘图pdf文件//绘图渐变效果)
- arcgis for flex 学习笔记(一)
- javascript的阻塞机制
- Google开源命令行参数解析库gflags