一眼匈牙利，没有紫啊
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
int n,m,res,a[205][205],p[40005];
int id1[205][205],fr1[40005],cnt1,id2[205][205],fr2[40005],cnt2;
bool vis[40005];
struct edge{
int v,nx;
}e[40005];
int cnt,hd[40005];
void add(int u,int v){
e[++cnt]=edge{v,hd[u]};
hd[u]=cnt;
}
vector<int> s;
bool match(int u){
for(int i=hd[u];i;i=e[i].nx){
int v=e[i].v;
if(vis[v])continue;
s.pb(v);vis[v]=1;
if(!p[v] || match(p[v])){
p[v]=u;
return 1;
}
}
return 0;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++)a[i][0]=2;
for(int i=0;i<=m;i++)a[0][i]=2;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(a[i][j]==2)continue;
if(a[i][j-1]!=2)id1[i][j]=id1[i][j-1];
else id1[i][j]=++cnt1,fr1[cnt1]=i;
if(a[i-1][j]!=2)id2[i][j]=id2[i-1][j];
else id2[i][j]=++cnt2,fr2[cnt2]=j;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(!a[i][j])
add(id1[i][j],id2[i][j]);
for(int i=1;i<=cnt1;i++){
if(match(i))res++;
for(int j:s)vis[j]=0;
s.clear();
}
// for(int i=1;i<=cnt2;i++)printf(" %d",p[i]);puts("");
printf("%d\n",res);
for(int i=1;i<=cnt2;i++)
if(p[i])
printf("%d %d\n",fr1[p[i]],fr2[i]);
return 0;
}
不要忘记函数返回值
不要忘记函数返回值
不要忘记函数返回值
标签：cnt,205,int,每日,vis,40005,P1263,一题,hd From： https://www.cnblogs.com/kentsbk/p/18318909