题解：匈牙利算法求解击打顺序

题意理解

有 (n) 次击打操作，每次操作必须选择一根柱子，每根柱子只能被击打一次。题目给出每次操作可能的柱子集合（(k_i \leq 2)），要求找到一个合法的击打顺序（一个 (1) 到 (n) 的排列）。如果不存在合法解，输出 "kou is angry"。

问题转化

这是一个二分图完美匹配问题：

• 左部：(n) 次操作（第 1 次、第 2 次、...、第 (n) 次）
• 右部：(n) 根柱子（编号 1 到 (n)）
• 边：如果第 (i) 次操作可以击打柱子 (j)，则从 (i) 到 (j) 连一条边

目标：找到一组完美匹配，使得每次操作对应一根不同的柱子。

算法思路（匈牙利算法）

1. 建图：读入数据，第 (i) 次操作向所有可选的柱子连边
2. 匹配：依次为每次操作寻找匹配的柱子 用 vis[] 数组记录本次 DFS 中已访问的柱子，避免重复如果当前柱子未被匹配，或匹配该柱子的操作可以重新匹配到其他柱子，则匹配成功
3. 判断无解：如果某次操作找不到匹配，输出 "kou is angry"
4. 输出结果：匹配完成后，ans[柱子] = 操作，需要转换成 a[操作] = 柱子 输出

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const int M=100010;
vector<int> v[M];
int n;
bool vis[M];
int ans[M];
int dfs(int x){
    for(int i=0;i<(int)v[x].size();++i){
        if(vis[v[x][i]])continue;
        vis[v[x][i]]=true;
        if(ans[v[x][i]]==0||dfs(ans[v[x][i]])){
            ans[v[x][i]]=x;
            return 1;
        }
    }
    return 0;
}
int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i){
        int cnt;cin>>cnt;
        for(int j=0;j<cnt;++j){
            int x;cin>>x;
            v[i].push_back(x);
        }
    }
    for(int i=1;i<=n;++i){
        memset(vis,false,sizeof(vis));
        if(dfs(i)==0){
            cout<<"kou is angry";
            return 0;   
        }
    }
    vector<int> a(n+1,0);
    for(int i=1;i<=n;++i){
        a[ans[i]]=i;
    }
    for(int i=1;i<=n;++i){
        cout<<a[i]<<" ";
    }
    return 0;
}

代码说明

• v[i]：第 (i) 次操作可以击打的柱子列表
• vis[]：DFS 中标记柱子是否被访问
• ans[]：ans[柱子] = 操作，表示该柱子被哪次操作匹配
• dfs(x)：为第 (x) 次操作寻找匹配的柱子，返回 1 表示成功，0 表示失败
• 匹配完成后，通过 a[ans[i]] = i 将 ans[柱子] = 操作 转换为 a[操作] = 柱子，最后输出 a[1] 到 a[n]

时间复杂度

• 每次 DFS 最多遍历所有边，总复杂度 (O(n \cdot m))
• 由于 (k_i \leq 2)，边数 (m \leq 2n)，最坏情况 (O(n^2))