HDU 3081 Marriage Match II 最大流OR二分匹配
2024-09-05 09:49:38
Marriage Match IIHDU - 3081
题目大意:每个女孩子可以和没有与她或者是她的朋友有过争吵的男孩子交男朋友,现在玩一个游戏,每一轮每个女孩子都要交一个新的男朋友,问最多可以玩多少轮?
首先要想知道每个女孩子能够和哪些男孩子交朋友,就得通过并查集来处理了,每个女孩子可以交朋友的男孩子,和她是朋友的女孩子同样可以交。
然后就是怎么知道能玩几轮。有两个方法。第一个就是最大流。
具体思路就是二分答案,每个女孩子都可以和能和他交朋友的男孩子建一条流量为1的边,就代表可以和他交一次朋友,然后源点与每个女孩子连一条流量为当前二分的这个答案的边,汇点也与每个男孩子连一条流量为当前二分的这个答案的流,这样的话能每个女孩子能够满流的话就是能够玩这么多轮,当前答案是符合的。
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int N=,M=,inf=;
struct Side{
int v,ne,w;
}S[M];
int n,sn,sb,se,head[N],dep[N],cur[N],fa[N],ok[N][N];
void init()
{
sn=;
sb=,se=*n+;
for(int i=sb;i<=se;i++)
head[i]=-;
}
void add(int u,int v,int w)
{
S[sn].w=w;
S[sn].v=v;
S[sn].ne=head[u];
head[u]=sn++;
}
void addE(int u,int v,int w)
{
add(u,v,w);
add(v,u,);
}
int gui(int x){
return fa[x]==x ? x : fa[x]=gui(fa[x]);
}
void bing(int x,int y)
{
int gx=gui(x),gy=gui(y);
if(gx!=gy)
fa[gx]=gy;
}
void bulidE(int limit)
{
init();
for(int i=;i<=n;i++)
addE(sb,i,limit);
for(int i=;i<=n;i++)
addE(n+i,se,limit);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(ok[i][j])
addE(i,n+j,);
}
bool bfs()
{
for(int i=sb;i<=se;i++)
dep[i]=;
dep[sb]=;
queue<int> q;
q.push(sb);
int u,v;
while(!q.empty()){
u=q.front();
q.pop();
for(int i=head[u];~i;i=S[i].ne){
v=S[i].v;
if(S[i].w>&&!dep[v]){
dep[v]=dep[u]+;
if(v==se)
return true;
q.push(v);
}
}
}
return false;
}
int dfs(int u,int minf)
{
if(u==se||!minf)
return minf;
int v,flow;
for(int &i=cur[u];~i;i=S[i].ne){
v=S[i].v;
if(S[i].w>&&dep[v]==dep[u]+){
flow=dfs(v,min(minf,S[i].w));
if(flow>){
S[i].w-=flow;
S[i^].w+=flow;
return flow;
}
}
}
return ;
}
int dinic()
{
int maxf=,flow;
while(bfs()){
for(int i=sb;i<=se;i++)
cur[i]=head[i];
while(flow=dfs(sb,inf))
maxf+=flow;
}
return maxf;
}
int solve()
{
int l=,r=n,mid,ans=;
while(l<=r){
mid=(l+r)>>;
bulidE(mid);
if(dinic()==n*mid)
ans=mid,l=mid+;
else
r=mid-;
}
return ans;
}
int main()
{
int t,m,f,a,b;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&f);
for(int i=;i<=n;i++){
fa[i]=i;
for(int j=;j<=n;j++)
ok[i][j]=;
}
while(m--){
scanf("%d%d",&a,&b);
ok[a][b]=;
}
while(f--){
scanf("%d%d",&a,&b);
bing(a,b);
}
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
for(int k=;k<=n;k++)
if(gui(i)==gui(j)&&ok[i][k])
ok[j][k]=;
printf("%d\n",solve());
}
return ;
}
最大流
第二种就是二分匹配。我们每次跑一遍匈牙利为每个女孩子匹配一个男孩子,然后再把他们的关系去掉继续匹配 ,最多能匹配多少轮,就是能玩多少轮。
#include<cstdio>
const int N=;
int n,fa[N],ok[N][N],vis[N],pp[N];
int gui(int x){
return fa[x]==x ? x : fa[x]=gui(fa[x]);
}
void bing(int x,int y)
{
int gx=gui(x),gy=gui(y);
if(gx!=gy)
fa[gx]=gy;
}
int match(int u)
{
for(int i=;i<=n;i++){
if(!vis[i]&&ok[u][i]){
vis[i]=;
if(!pp[i]||match(pp[i])){
pp[i]=u;
return ;
}
}
}
return ;
}
int solve()
{
int ans=,mm;
while(){
mm=;
for(int i=;i<=n;i++){
for(int j=;j<=n;j++)
vis[j]=;
mm+=match(i);
}
if(mm==n)
ans++;
else
break;
for(int i=;i<=n;i++){
ok[pp[i]][i]=;
pp[i]=;
}
}
return ans;
}
int main()
{
int t,m,f,a,b;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&f);
for(int i=;i<=n;i++){
fa[i]=i;
pp[i]=;
for(int j=;j<=n;j++)
ok[i][j]=;
}
while(m--){
scanf("%d%d",&a,&b);
ok[a][b]=;
}
while(f--){
scanf("%d%d",&a,&b);
bing(a,b);
}
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
for(int k=;k<=n;k++)
if(gui(i)==gui(j)&&ok[i][k])
ok[j][k]=;
printf("%d\n",solve());
}
return ;
}
二分匹配
最新文章
- servlet文件下载
- 逻辑回归LR
- C# Socket系列一 简单的创建socket的监听
- Activity之多启动图标
- 删除空文件夹 清除CS扩展名文件 bat
- Gabor学习笔记
- CSS系列:表达式(Expression)`淘汰`
- JAVA操作数据库插入中文表中显示乱码的解决方法
- 利用OPENSSL 实现MD5加密。
- Web Services的相关名词解释:WSDL与SOAP
- HDU1150 Machine Schedule(二分图最大匹配、最小点覆盖)
- Part 3:视图和模板--Django从入门到精通系列教程
- FusionCharts封装-Category
- Oracle 并发创建索引
- Oracle使用学习笔记(二)_Sql语句
- spring boot、cloud v2.1.0.RELEASE 使用及技术整理
- Python内置类型(3)——比较
- mysql 临时数据突然变大
- python 一次创建多级目录
- 利用github搭建个人maven仓库
热门文章
- N分成不同的数相乘使答案最大
- Synchronized&;Lock&;AQS详解
- Python基础 第四章 字典(2)字典方法&;章小结
- 第十章 ZYNQ-MIZ701 DDR3 PS读写操作方案
- volatile 关键字(修饰变量)
- DIP原则
- 爬虫遇到IP访问频率限制的解决方案
- 单变量图形的pandas方法
- MySQL5.7 启动报错:initialize specified but the data directory has files in it. Aborting.
- Linux目录结构以及一些常见操作