题意概述
给定一个 \(n\) 个节点的竞赛图，需要把所有点划分成三个集合 \(A,B,C\)，满足:
-
若 \(x \in A,y \in B\) ，则边方向为 \(x\) 到 \(y\) 。
-
若 \(x \in B,y \in C\) ，则边方向为 \(x\) 到 \(y\) 。
-
若 \(x \in C,y \in A\) ，则边方向为 \(x\) 到 \(y\) 。
\(3 \le n \le 500\) 。
思路
如果存在合法的方案，该方案唯一。假设当前分组方案合法，除了所有元素都循环移动一组，其他移动均不合法，而循环移动相当于没有移动，因此方案唯一。
得到这个性质后，就可以比较随意地构造了。
先找到一个三元组 \(x,y,z\) ，满足 \(x\)->\(y\)->\(z\)->\(x\) ，将 \(x,y,z\) 分别分配到 \(1,2,3\) 号组。枚举所有元素，尝试加入其中一个组，因为方案唯一，可加入的组最多只有一个。如果没有组可以加入，考虑调整已加入元素。
此时唯一的调整方案为把三组合并成一组。合并之后，枚举剩下的元素，找到一个合法二元组 \(a,b\) 分别填充到第 \(2\) 组和第 \(3\) 组，如果找不到则无解。回退一位重新判断本位元素即可。
因为方案唯一，当发现某元素加不进去的时候，当前方案一定是错的，因此尝试重构是正确的。
时间复杂度 \(\mathcal{O}(n^3)\) 。
代码
//author:kzssCCC#include <bits/stdc++.h>
using namespace std;
using ll = long long;void solve(){int n;cin >> n;vector<vector<int>> a(n+1,vector<int>(n+1));for (int i=1;i<=n;i++){for (int j=i+1;j<=n;j++){cin >> a[i][j];}}for (int i=1;i<=n;i++){for (int j=1;j<i;j++){a[i][j] = a[j][i]^1;}}vector<bool> vis(n+1,false);bool ok = false;vector<vector<int>> res(4);for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){if (j==i) continue;for (int k=1;k<=n;k++){if (k==i || k==j) continue;if (a[i][j]==1 && a[j][k]==1 && a[k][i]==1){ok = true;vis[i] = vis[j] = vis[k] = true;res[1].push_back(i);res[2].push_back(j);res[3].push_back(k);break;}}if (ok) break;}if (ok) break;}if (!ok){cout << "0 0 0" << '\n';return;}for (int i=1;i<=n;i++){if (vis[i]) continue;bool ok2 = false;for (int j=1;j<=3;j++){bool ok3 = true;for (auto& d:{-1,1}){for (auto& v:res[(j+d-1+3)%3+1]){if (d==1 && a[i][v]==0 || d==-1 && a[v][i]==0){ok3 = false;break;}}if (!ok3) break;}if (ok3){ok2 = true;res[j].push_back(i);break;}} if (!ok2){for (auto& v:res[2]){res[1].push_back(v);}for (auto& v:res[3]){res[1].push_back(v);}res[2].clear();res[3].clear();bool ok3 = false;for (int p=i;p<=n;p++){if (vis[p]) continue;for (int q=i;q<=n;q++){if (vis[q] || p==q || a[p][q]!=1) continue;bool ok4 = true;for (auto& v:res[1]){if (!(a[v][p]==1 && a[p][q]==1 && a[q][v]==1)){ok4 = false;break;}}if (ok4){vis[p] = vis[q] = true;res[2].push_back(p);res[3].push_back(q);ok3 = true;break;}}if (ok3){break;}}if (!ok3){cout << "0 0 0" << '\n';return;} i--; }}for (int j=1;j<=3;j++){cout << res[j].size() << ' ';}cout << '\n';for (int j=1;j<=3;j++){for (auto& v:res[j]){cout << v << ' ';}cout << '\n';}
}int main(){ios::sync_with_stdio(false);cin.tie(0);int t = 1;// cin >> t;while (t--) solve();return 0;
}