匈牙利算法模板

P3386 【模板】二分图最大匹配 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路:最模板的一集.还未匹配则匹配，否则之前一个给现在这个让位置.

int n,m,e;
vector<int> vct[505];
int match[505];
bool vis[505];
bool mark[505][505];
bool dfs(int s){for(auto v:vct[s]){if(vis[v]) continue;vis[v]=1;if(!match[v]||dfs(match[v])){   女生没有伴侣，或者其伴侣可以选择其他女生match[v]=s;return 1;}}return 0;
}
void solve(){               匈牙利🇭🇺--求最大匹配 o(n*m)cin>>n>>m>>e;for(int i=1;i<=e;i++){int u,v; cin>>u>>v;if(!mark[u][v]){vct[u].emplace_back(v);    建单向边mark[u][v]=1;}}int ans=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) vis[j]=0;if(dfs(i)) ans++;}cout<<ans;
}

C-有大家喜欢的零食吗_河南萌新联赛2024第（一）场：河南农业大学 (nowcoder.com)

思路:纯模板.

int n;
vector<int> vct[505];
int match[505],vis[505];
bool dfs(int s){for(auto v:vct[s]){if(vis[v]) continue;vis[v]=1;if(!match[v]||dfs(match[v])){    如果女生没有伴侣，或者其伴侣可以选择其他女生match[v]=s;    糖果v被s孩子选了return 1;}}return 0;
}
有大家喜欢的零食吗
https://ac.nowcoder.com/acm/contest/86639/C
void solve(){               C   匈牙利🇭🇺--求最大匹配cin>>n;for(int i=1;i<=n;i++){int k; cin>>k;for(int j=1;j<=k;j++){      孩子选糖果int x; cin>>x;vct[i].emplace_back(x);}}int ans=0;for(int i=1;i<=n;i++){if(dfs(i)) ans++;for(int j=1;j<=n;j++) vis[j]=0; init}if(ans==n) cout<<"Yes";else cout<<"No"<<endl<<n-ans;
}

[ABC091C] 2D Plane 2N Points - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路:纯模板

int n;
pair<int,int> a[150];
pair<int,int> b[150];
vector<int> vct[105];
int match[105];
bool vis[105];
bool dfs(int s){for(auto v:vct[s]){if(vis[v]) continue;vis[v]=1;if(!match[v]||dfs(match[v])){     如果女生没有伴侣，或者其伴侣可以选择其他女生match[v]=s;return 1;}}return 0;
}
2D Plane 2N Points
https://www.luogu.com.cn/problem/AT_arc092_a
void solve(){  B--匈牙利cin>>n;for(int i=1;i<=n;i++) cin>>a[i].first>>a[i].second;for(int i=1;i<=n;i++) cin>>b[i].first>>b[i].second;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(a[i].first<b[j].first&&a[i].second<b[j].second) vct[i].emplace_back(j);}}int ans=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++) vis[j]=0;if(dfs(i)) ans++;}cout<<ans;
}