CF1815C 题解

## 思路 首先看到这种二元组的问题，可以先连边。在这个问题中是 $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$。 ## 代码 ```cpp #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; } ```