就是跑匈牙利算法就行了，难点完全在于建图。
模板水题
#include <bits/stdc++.h>
const int N=510;
int n,m,e;
int G[N][N],match[N];
std::bitset<N> vis;
namespace BlackWhiteGraph{
inline void Init(void){
scanf("%d%d",&n,&m);
int a,t;
for(register int i=1;i<=n;++i){
scanf("%d",&t);
while(t--)
scanf("%d",&a),
G[i][a]=1;
}
}
bool dfs(int u){
for(register int i=1;i<=m;++i){
if(!vis[i]&&G[u][i]){
vis[i]=true;
if(!match[i]||dfs(match[i])){
match[i]=u;
return true;
}
}
}
return false;
}
int ans=0;
void Match(void){
for(register int i=1;i<=n;++i){
vis.reset();
if(dfs(i))++ans;
}
}
void output(void){
printf("%d\n",ans);
exit(0);
}
}
using namespace BlackWhiteGraph;
int main(){
Init();
Match();
output();
}
直接无脑套板子然后无脑匈牙利就 \(AC\) 了。
#include <bits/stdc++.h>
#define add push_back
using namespace std;
const int N=10100;
int n,m;
vector<int> G[N];
int match[N],use[N];
bitset<N> vis;
bool dfs(int u){
for(int v : G[u]){
if(!vis[v]){
vis[v]=true;
if(!match[v] || dfs(match[v])){
use[u]=v,match[v]=u;
return true;
}
}
}
return false;
}
int main(){
int ans=0;
scanf("%d%d",&m,&n);
int a,b;
scanf("%d%d",&a,&b);
while(a!=-1&&b!=-1){
G[a].add(b);
scanf("%d%d",&a,&b);
}
for(register int i=1;i<=n;++i){
vis.reset();
ans+=dfs(i);
}
printf("%d\n",ans);
for(register int i=1;i<=n;++i){
if(use[i])
printf("%d %d\n",i,use[i]);
}
exit(0);
}
相比于上一道题这道题要记录路径，因为匈牙利模板自带存储路径，直接输出就行了，为什么这个东西也能进\(24\)题
稍带思维的省选题
四川省选 \(Day2\ T3\)，但是水得很，直接把两个属性和物品绑在一起然后一步一步跑匈牙利就 \(AC\).
但是这道题还是有一些细节什么的，要匈牙利比较熟悉原理才能 \(AC\).
#include "bits/stdc++.h"
#define ll long long
#define add push_back
using namespace std;
const int N=1e6+10;
int n,m,col;
int vis[N],match[N];
vector<int> G[N];
bool dfs(int u){
for(int v:G[u])
if(vis[v]!=col){
vis[v]=col;
if(!match[v] || dfs(match[v])){
match[v]=u;
return true;
}
}
return false;
}
int main(){
scanf("%d",&n);
int mx=-1;
for(register int i=1;i<=n;++i){
int u,v;
scanf("%d%d",&u,&v);
G[u].add(i);
G[v].add(i);
}
for(register int i=1;i<N;++i){
++col;if(!dfs(i)){
printf("%d\n",col-1);
break;
}
}
return 0;
}
上一题输出路径 \(AC\)
很难很难的省选题
鸽。