CF1815C 题解

王熙文 · 2023-06-03 11:57:00 · 题解

思路

首先看到这种二元组的问题，可以先连边。在这个问题中是 a_i 向 b_i 连一条有向边。

可以思考什么时候数列无限长。猜测当有数在有向图上不能走到 1 时数列无限长。可以把所有在有向图上不能走到 1 的数拿出来，设其为 b_1,b_2,\cdots,b_m，那么 b 里面每个数向外连的边也一定在 b 里。构造 1,b_1,b_2,\cdots,b_m,b_1,b_2,\cdots,b_m,\cdots 即可。

若不是这种情况，则每个数都直接或间接被 1 限制。显然与 1 最短距离为 dis 的数最多可以放 dis+1 个。考虑按照以下的方式构造：按照与 1 的最短距离（设其为 dis）从小到大插入序列。最初有一个数 1。之后将 dis=1 的数插入到 1 的两边。接下来将 dis=2 的数插入到每一个 dis=1 的数前面和整个序列的最后。以此类推，dis=x 的数插入到每一个 dis=x-1 的数前面和整个序列的最后。这样构造对于 dis=x 的数插入了 x+1 遍，因此一定是最优的。

注意，对于 dis=x 的数每次插入的顺序应当是一样的，否则会出问题，原因见下文。

为什么这样的构造满足要求呢？

• 对于 dis 较大的数连向 dis 较小的数，一定有前者的 dis 为后者的 dis+1，那么在插入的过程中就能保证 dis 较大的数相邻两个之间都有且仅有一个 dis 较小的数。
• 对于 dis 相同的数有连接，因为每次插入的顺序是一样的，所以也可以保证。
• 对于 dis 较小的数连向 dis 较大的数，可以发现每次插入 dis 较大的数时一定有数在任意一对 dis 较小的数中间，因此也能保证。可以手摸一下样例以保证完全理解。

不必用程序模拟这样的过程。手摸后可以发现，设 c_x 为 dis=x 的数组成的数列，d_x 为 c_n,c_{n-1},\cdots,c_x，则最终的数列为：d_1,1,d_1,d_2,\cdots,d_n。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> e1[1510];
queue<int> q;
int dis[1510];
vector<int> e2[1510];
int tot,ans[2000010];
int main()
{
    int t; cin>>t; while(t--)
    {
        cin>>n>>m;
        for(int i=1; i<=n; ++i) e1[i].clear();
        for(int i=1; i<=m; ++i)
        {
            int u,v; cin>>u>>v;
            e1[v].push_back(u);
        }
        memset(dis,0x3f,sizeof(dis));
        dis[1]=0,q.push(1);
        while(!q.empty())
        {
            int frn=q.front(); q.pop();
            for(int v:e1[frn])
            {
                if(dis[v]>=1e9) dis[v]=dis[frn]+1,q.push(v);
            }
        }
        bool flag=0;
        for(int i=1; i<=n; ++i) flag|=(dis[i]>=1e9);
        if(flag) { cout<<"INFINITE\n"; continue; }
        cout<<"FINITE\n";
        for(int i=1; i<=n; ++i) e2[i].clear();
        for(int i=1; i<=n; ++i) e2[dis[i]].push_back(i);
        tot=0;
        for(int i=n; i>=1; --i) for(int j:e2[i]) ans[++tot]=j;
        ans[++tot]=1;
        for(int i=1; i<=n; ++i)
        {
            for(int j=n; j>=i; --j)
            {
                for(int k:e2[j]) ans[++tot]=k;
            }
        }
        cout<<tot<<'\n';
        for(int i=1; i<=tot; ++i) cout<<ans[i]<<' '; cout<<'\n';
    }
    return 0;
}