小红开宝箱

时间限制：1秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

小红来到了一个宝箱面前，但这个宝箱上锁了，开这个宝箱需要进行解密。

解密的方式是：给出了 $n$ 根柱子，小红必须按照规定的次序依次击打这 $n$ 根柱子。

现在小红通过贿赂地下城的设计者小紫，得出了每次应击打的柱子的可能性。小红想让你帮忙设计一个击打顺序，使得该顺序和小紫给出的信息不冲突。

输入描述：

第一行输入一个正整数 $n$ ，代表柱子的数量。
接下来的 $n$ 行，每行首先输入一个正整数 $k_i$ ​，代表对于第 $i$ 次击打小紫给出的信息（柱子的可能性）数量。紧接着是 $k_i$ 个正整数 $p_{i}j$ ​，代表该次击打有可能是哪一个柱子。
$1\le n\le 10^5$
$1\le k_i\le 2$
$1\le p_{ij}\le n$

输出描述：

如果不存在一个合法解，代表小紫欺骗了小红，请输出 $"kouisangry"$ 。否则输出一个长度为 $n$ 的排列，代表一个合法的击打序列。有多解时输出任意即可。

示例1

输入：

3
1 2
2 1 3
2 1 3

输出：

2 1 3

说明：

输出 $231$ 也是可以的。

解题思路

本题核心是二分图最大匹配求解合法击打序列：问题本质是为n个击打位置分配n个互不重复的柱子，且第i个位置只能选择指定的 $1\tilde{}2$ 个柱子，等价于求解二分图的完美匹配。构建二分图，左部节点为击打位置，右部节点为柱子，为每个位置向其可选的柱子连边；采用匈牙利算法求解最大匹配，若匹配数等于n，则存在合法解，否则输出无解。根据匹配结果映射关系，直接输出合法的排列即可。由于每个位置最多连 $2$ 条边，算法效率极高，完美适配n≤1e5的大数据规模。

总结

1. 核心逻辑：将分配问题转化为击打位置-柱子的二分图完美匹配问题。
2. 关键操作：匈牙利算法求解最大匹配，匹配数为n则构造解，否则判定无解。
3. 效率保障：每个节点边数不超过 $2$ ，算法运行速度快，满足题目时间限制。

代码内容

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<ll>> vt;
typedef pair<ll,ll> pll;
const ll N=2e5+10;
const ll mod=1e9+7;
const ll INF=1e18;
bool v[N];
ll m[N];
vector<ll> tr[N];

bool dfs(ll x)
{
    for(auto& to:tr[x])
    {
        if(v[to]) continue;
        v[to]=1;

        if(!m[to]||dfs(m[to]))
        {
            m[to]=x;
            return 1;
        }
    }
    return 0;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    ll n;
    cin>>n;
    for(ll i=1;i<=n;i++)
    {
        ll k;cin>>k;
        for(ll j=1;j<=k;j++)
        {
            ll x;
            cin>>x;
            tr[x].push_back(i+n);
        }
    }

    ll ans=0;
    for(ll i=1;i<=n;i++)
    {
        memset(v,0,sizeof v);
        if(dfs(i)) ans++;
    }

    if(ans!=n)
    {
        cout<<"kou is angry"<<endl;
        return 0;
    }

    for(ll i=1;i<=n;i++) cout<<m[i+n]<<" ";
    cout<<endl;

    return 0;
}