题解 | #小红开宝箱#

本题大致题意是，给出打击柱子数量即打击次数，然后给出每次打击中可能的目标对象，然后确定一个合理的打击序列，这让我们想到了基于二分图匹配的匈牙利算法：确定一个元素的匹配值，如果匹配值已经有其他元素占领，那么让占领此匹配值的元素换一个匹配值，最终达到一个合理的匹配。代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int a[N][3];
int e[N<<1],ne[N<<1],h[N],idx,match[N<<1];
bool st[N];
void add(int a,int b)//链式前向星存图
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool dfs(int u)
{
    for(int i=h[u];~i;i=ne[i])//找邻接点
    {
        int j=e[i];
        if(st[j])continue;//已经被访问
        st[j]=true;
        if(!match[j]||dfs(match[j]))//未匹配或者可以让已经占领此柱子的元素换一个匹配值
        {
            match[j]=u;
            return true;
        }
    }
    return false;
}
int main()
{
    int n;
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++)
    {
        int k;
        cin>>k;
        for(int j=1;j<=k;j++)
        {
            int w;
            cin>>w;
            add(w,i);   //柱子w可以在第i次打
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
         memset(st,false,sizeof st);//每次都要把标记数组复原
        if(dfs(i))ans++;//记录匹配数量
    }
    if(ans!=n)//只有匹配数量为n时，才能有合理的匹配的结果
    {
        puts("kou is angry");
        return 0;
    }
    for(int i=1;i<=n;i++)cout<<match[i]<<" ";
    return 0;
}

如果不太明白此算法，可以找匈牙利算法的相关知识