【题解】[牛客OI周赛3-提高组]C.爆瓶子 二分图匹配
学习了大佬代码，毕竟本蒟蒻至今写不来二分图匹配（NOIP退役预定qwq）
#include<cstdio>
#include<cstring>
const int N=500;
int t,n,m,g[N][N],hd[N],tot,To[N],match[N],vis[N],lim;
struct Edge{
int v,nx;
}e[N*N];
inline void add(int u,int v)
{
e[++tot].v=v;
e[tot].nx=hd[u];
hd[u]=tot;
}
inline int dfs(int x)
{
for(int i=hd[x];i;i=e[i].nx)
if(!vis[e[i].v])
{
vis[e[i].v]=1;//不要在外面写vis[x]=1，x上没有vis标记
if(!match[e[i].v]||(match[e[i].v]>lim&&dfs(match[e[i].v])))
{
match[e[i].v]=x;
To[x]=e[i].v;
return 1;
}
}
return 0;
}
inline void solve()
{
memset(hd,0,sizeof(hd));tot=0;
for(int i=1;i<=n;i++)
for(int j=n;j>=1;j--)
if(g[i][j])add(i,j+n);
//左边的点编号1~n
//右边的点编号n+1~2n
memset(To,0,sizeof(To));
memset(match,0,sizeof(match));
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
if(!To[i])lim=0,dfs(i);
}
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
for(int j=hd[i];j;j=e[j].nx)
{
if(To[i]==e[j].v)break;//没有找到更小的解
if(match[e[j].v]<i)continue;//已与先前匹配
int x=match[e[j].v],y=To[i];
To[x]=0;match[y]=0;To[i]=e[j].v;match[e[j].v]=i;
if(lim=i,dfs(x))break;//lim表示不能增广到确定匹配的i-e[j].v
To[x]=e[j].v;match[e[j].v]=x;To[i]=y;match[y]=i;
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g[i][j]=1;
for(int i=1;i<=m;i++)
for(int j=1,x;j<=n;j++)
{
scanf("%d",&x);
g[j][x]=0;
}
for(int i=1;i<=n-m;i++)
{
solve();
for(int j=1;j<=n;j++)
printf("%d ",To[j]-n),g[j][To[j]-n]=0;
puts("");
}
}
return 0;
}
总结
二分图匹配+字典序最小