[USACO22JAN] Cereal 2 S

lzqy_ · 2022-02-07 16:33:05 · 题解

二分图板子题。

考虑将牛作为一个点集，麦片作为一个点集。若奶牛 A 喜欢麦片 a，则 A 与 a 连边，这样建出的图显然是一个二分图。奶牛总数减二分图最大匹配数即为饥饿奶牛的最小个数。

注意，由于奶牛优先拿第一喜欢的麦片，所以在二分图匹配的时候，优先匹配第一喜欢的麦片。

至于最后输出的排列，只需要满足以下条件即可：

• 若奶牛 A 第一喜欢麦片 a，第二喜欢麦片 b，且奶牛 A 拿了麦片 b，奶牛 B 拿了麦片 a，则 B 在 A 前面。

• 若奶牛 A 第一喜欢麦片 a，第二喜欢麦片 b，且奶牛 B,C 拿了麦片 b,c，则 B,C 在 A 前面。

虽然看上去好像是拓扑，但递归输出就好了。

具体实现看代码。

#include<bits/stdc++.h>
using namespace std;
const int maxn=200010;
inline int read()
{
    int x=0;
    char c=getchar();
    for(;!(c>='0'&&c<='9');c=getchar());
    for(;c>='0'&&c<='9';c=getchar())
        x=(x<<1)+(x<<3)+c-'0';
    return x;
}
int n,m,ans[maxn];
int a[maxn],b[maxn];
int pp[maxn],vis[maxn];
bool dfs(int x,int t){
    if(vis[x]==t) return 0;
    vis[x]=t;
    if(!pp[a[x]]||dfs(pp[a[x]],t)){
   //优先拿麦片a[x](第一喜欢)
        pp[a[x]]=x,pp[x]=a[x];
        return 1;
    }
    else if(!pp[b[x]]||dfs(pp[b[x]],t)){
    //再拿麦片b[x](第二喜欢)
        pp[b[x]]=x,pp[x]=b[x];
        return 1;
    }
    return 0;
}
void Print(int x){//输出
    if(vis[x]) return ;
    vis[x]=1;//vis[x]=1:奶牛x已经输出过
    if(!pp[x]){
   //如果奶牛x没有拿走麦片
   //那么拿走它第一/二喜欢的麦片的奶牛要先输出
        Print(pp[a[x]]);
        Print(pp[b[x]]);
        printf("%d\n",x);
        return ; 
    }
    if(pp[x]==b[x]){
    //如果奶牛x拿走的是它第二喜欢的麦片
    //那么拿走它第一喜欢的麦片的奶牛要先输出
        Print(pp[a[x]]);
        printf("%d\n",x);
        return ;
    }
    //否则直接输出
    printf("%d\n",x);
}
int main(){
    int sum=0;
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        a[i]=read()+n,b[i]=read()+n;
    for(int i=1;i<=n;i++) dfs(i,i);//求二分图最大匹配
    for(int i=1;i<=n;i++) sum+=bool(pp[i]);
    printf("%d\n",n-sum);
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
        if(!vis[i]) Print(i);
    return 0;