匈牙利算法模板题(最大匹配)
链式前向星建图
#include<bits/stdc++.h>
using namespace std;
const int INF=200*200+10;
struct node{
int to,ne;
}edge[INF];
int head[INF],vis[INF],match[INF];
int tot=0;
void add(int u,int v){
++tot;
edge[tot].to=v;
edge[tot].ne=head[u];
head[u]=tot;
}
bool find(int x){
for(int i=head[x];~i;i=edge[i].ne){
int to=edge[i].to;
if(!vis[to]){
vis[to]=1;
if(!match[to]||find(match[to])){
match[to]=x;
return true;
}
}
}
return false;
}
int main(){
int T;
cin>>T;
while(T--){
tot=0;
memset(head,-1,sizeof(head));
memset(match,0,sizeof(match));
int n;
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int x;
cin>>x;
if(x==1) add(i,j+n);
}
}
int ans=0;
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(!vis[i]){
if(find(i)) ans++;
}
}
if(ans>=n) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
二维数组建图
#include<bits/stdc++.h>
using namespace std;
const int INF=200+10;
int mp[INF][INF],vis[INF],ma[INF];
int n;
bool find(int x){
for(int i=1;i<=n;i++){
if(mp[x][i]&&!vis[i]){
vis[i]=1;
if(!ma[i]||find(ma[i])){
ma[i]=x;
return true;
}
}
}
return false;
}
int main(){
int T;
cin>>T;
while(T--){
cin>>n;
memset(ma,0,sizeof(ma));
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>mp[i][j];
}
}
int ans=0;
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(find(i)) ans++;
}
if(ans>=n) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}