当前位置: 首页 > news >正文

二分图最大匹配 输出具体方案

洛谷P2756

匈牙利算法:

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int match[N],vis[N];
int n,m;
vector<int> edges[N];
bool dfs(int u){for(int &v:edges[u]){if(vis[v])continue;vis[v]=true;if(!match[v]||dfs(match[v])){match[v]=u;return 1;}}return 0;
}
int main(){cin.tie(nullptr)->sync_with_stdio(false);cin>>m>>n;int u,v;while(cin>>u>>v,~u&&~v){edges[u].push_back(v);}int ans=0;for(int i=1;i<=m;i++){memset(vis,0,sizeof(vis));if(dfs(i))ans++;}cout<<ans<<endl;for(int i=m+1;i<=n;i++){if(match[i])cout<<match[i]<<' '<<i<<endl;}return 0;
}

dinic算法:

#include<bits/stdc++.h>
using namespace std;
const int N=110,M=((N*N)<<1)+(N<<1);
typedef long long LL;
struct edge{LL v,c,ne;}e[M];
int h[N],cur[N],dep[N],id=1;
int n,m,s,t;void add(int u,int v,int c){e[++id]={v,c,h[u]};h[u]=id;
}bool bfs(){memset(dep,0,sizeof(dep));queue<int> q;q.push(s);dep[s]=1;while(q.size()){int u=q.front();q.pop();for(int i=h[u];i;i=e[i].ne){int v=e[i].v;if(dep[v]==0&&e[i].c){dep[v]=dep[u]+1;q.push(v);if(v==t)return true;}}}return false;
}LL dfs(int u,LL mf){if(u==t)return mf;LL sum=0;for(int i=cur[u];i;i=e[i].ne){cur[u]=i;int v=e[i].v;if(dep[v]==dep[u]+1&&e[i].c){int f=dfs(v,min(mf,e[i].c));sum+=f;mf-=f;e[i].c-=f;e[i^1].c+=f;if(mf==0)break;}}if(sum==0)dep[u]=0;return sum;
}LL dinic(){LL flow=0;while(bfs()){memcpy(cur,h,sizeof(h));flow+=dfs(s,1e9);}return flow;
}int main(){cin.tie(nullptr)->sync_with_stdio(false);cin>>m>>n;int u,v;while(cin>>u>>v,~u&&~v){add(u,v,1);add(v,u,0);}s=0,t=n+1;for(int i=1;i<=m;i++){add(s,i,1);add(i,s,0);}for(int i=m+1;i<=n;i++){add(i,t,1);add(t,i,0);}cout<<dinic()<<endl;for(int u=1;u<=m;u++){for(int i=h[u];i;i=e[i].ne){int v=e[i].v;if(e[i].c||v==0)continue;else{cout<<u<<' '<<v<<endl;break;}}}return 0;
}

EK算法:

#include<bits/stdc++.h>
using namespace std;
const int N=110,M=((N*N)<<1)+(N<<1);
typedef long long LL;
struct edge{LL v,c,ne;}e[M];
int h[N],id=1,mf[N],pre[N];
int n,m,s,t;void add(int u,int v,int c){e[++id]={v,c,h[u]};h[u]=id;
}bool bfs(){memset(mf,0,sizeof(mf));queue<int> q;q.push(s);mf[s]=1e9;while(q.size()){int u=q.front();q.pop();for(int i=h[u];i;i=e[i].ne){int v=e[i].v;if(mf[v]==0&&e[i].c){mf[v]=min(1ll*mf[u],e[i].c);pre[v]=i;q.push(v);if(v==t)return true;}}}return false;
}LL EK(){LL flow=0;while(bfs()){int v=t;while(v^s){int i=pre[v];e[i].c-=mf[t];e[i^1].c+=mf[t];v=e[i^1].v;}flow+=mf[t];}return flow;
}int main(){cin.tie(nullptr)->sync_with_stdio(false);cin>>m>>n;int u,v;while(cin>>u>>v,~u&&~v){add(u,v,1);add(v,u,0);}s=0,t=n+1;for(int i=1;i<=m;i++){add(s,i,1);add(i,s,0);}for(int i=m+1;i<=n;i++){add(i,t,1);add(t,i,0);}cout<<EK()<<endl;for(int u=1;u<=m;u++){for(int i=h[u];i;i=e[i].ne){int v=e[i].v;if(e[i].c||v==0)continue;else{cout<<u<<' '<<v<<endl;break;}}}return 0;
}
http://www.hskmm.com/?act=detail&tid=26136

相关文章:

  • 我的联想小新潮7000笔记本的优化
  • Go语言之接口与多态 -《Go语言实战指南》 - 指南
  • 地球科学概论
  • 2025多校冲刺CSP模拟赛4 总结
  • 多路归并、败者树、置换-选择排序、最佳归并树
  • 看vue文档记录(未整理)
  • Spring5笔记
  • 50天50个前端项目 - HTML/CSS和JavaScript实战合集
  • [BalticOI 2002] Tennis Club (Day1) 解题报告
  • 党徽
  • ZKEACMS:基于ASP.Net Core开发的开源免费内容管理系统
  • MySQL面试题汇总
  • 穷人的中国象棋打谱程序
  • 文件系统的层次结构
  • oracle 19c学习笔记2
  • 文件保护
  • 一些数数杂题
  • AI元人文:规则与人文的统一之路
  • 10.7
  • qmd 模拟赛的一道题
  • 四元数:从理论基础到实际应用的深度探索 - 教程
  • Day12
  • HoneyWell(霍尼韦尔)1450g扫码枪说明书
  • 课上动手东脑问题
  • 箭头函数的疑问
  • 文件共享
  • 【万字长文】让面试没有难撕的JS基础题
  • Java总览
  • PCoT: Persuasion-Augmented Chain of Thought for Detecting Fake News and Social Media Disinformation
  • 博客地址