洛谷 1894 [USACO4.2]完美的牛栏The Perfect Stall
2024-08-30 23:07:57
【题解】
其实是个二分图最大匹配的模板题,直接上匈牙利算法就好了。
#include<cstdio>
#include<algorithm>
#define N 1010
#define rg register
using namespace std;
int n,m,E,ans,T,tot,last[N],v[N],from[N];
struct edge{
int to,pre;
}e[N*N];
inline int read(){
int k=,f=; char c=getchar();
while(c<''||c>'')c=='-'&&(f=-),c=getchar();
while(''<=c&&c<='')k=k*+c-'',c=getchar();
return k*f;
}
int dfs(int x){
for(rg int i=last[x],to;i;i=e[i].pre) if(v[to=e[i].to]!=T){
v[to]=T;
if(!from[to]||dfs(from[to])){
from[to]=x;
return ;
}
}
return ;
}
int main(){
n=read(); m=read();
for(rg int i=;i<=n;i++){
int num=read();
for(rg int j=;j<=num;j++){
int v=read();
e[++tot]=(edge){v,last[i]};last[i]=tot;
}
}
for(rg int i=;i<=n;i++) ++T,ans+=dfs(i);
printf("%d\n",ans);
return ;
}
最新文章
- Date类
- Spring学习总结(一)——Spring实现IoC的多种方式
- 解决maven项目移动
- 学习simple.data之基础篇
- GROUPING SETS、CUBE、ROLLUP
- 列表:一个打了激素的数组2 - 零基础入门学习Python011
- linux用户管理最常用的三个文件说明(不完整版)
- 25 python 初学(socket,socketserver)
- Java方法的静态绑定与动态绑定讲解(向上转型的运行机制详解)
- VC.【转】窗口置于前台并激活的方法
- UI Recorder 安装教程(二)
- spark数据倾斜
- Ubuntu 12.04常用快捷键
- springboot2.X集成HttpClient 发送HTTPS 请求
- Scrapyd-Client的安装
- bzoj 3884 欧拉定理
- mysql5.7
- 关于comet
- python使用multiprocessing进行多进程编程(1)
- 详解TCP建立连接全过程