自动搬运

查看原文

来自洛谷，原作者为

	wjwWeiwei 给 NATO ✌✌磕头了

搬运于2025-08-24 23:07:16，当前版本为作者最后更新于2024-12-21 15:11:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言：很好的题，校内选拔 EC final 打星队时靠此题打到了 rank 2。

先跳了 T4 看这道题。可以观察到限制很宽松，找到一半的三角形就可以了，于是可以先想一个贪心思路：枚举边集中的一条边 $AB$，并找到另一个点 $C$ 使得 $AC$ 与 $BC$ 联通，并删除这三个点。

不过这显然会被如下的情况卡掉：

这样的话，找到一个三角形后，3 个同时会被破坏，找到的三角形个数最坏为 $\lceil\frac{2n}{3}\rceil$ 个，不过也很接近 $n$。

所以可以考虑打乱加入的点，使得上述情况不会出现太多。在随机数据下这样贪心成功的概率极高。本地造出 $n=300$ 的数据基本能找到 $>550$ 个三角形。

当然基于图中的那种情况有一个 $O(n^4)$ 的方法，可以解决小数据不打散点列时成功概率比较低的情况，不过这没有必要就是了。

官方 solution 说可以用 flow 找到所有三角形，不过我也不是很会。

赛事代码（去掉部分分）：

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
const int N=1e5+5;
int n,m;
int T;
int id[N];
int cnt=0;
bool vis[N];
unordered_map<int,int>um[N];
struct node{
	int u,v,w;
};
vector<node>ans;
bool fl=0;
int main(){
	srand(time(0));
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m;
		cnt=0;
		int up=6*n;
		int u,v;
		for(int i=1;i<=up;i++)um[i].clear();
		for(int i=1;i<=m;i++){
			cin>>u>>v;
			um[u][v]=um[v][u]=1;
		}
		cnt=0;
		while(cnt^n){
			ans.clear();
			cnt=0;
			for(int i=1;i<=up;i++)id[i]=i,vis[i]=0;
			random_shuffle(id+1,id+1+up);
			for(int i=1;i<=up;i++){
				int x=id[i];
				if(vis[x])continue;
				for(int j=1;j<=up;j++){
					int y=id[j];
					if(x==y||vis[y]||!um[x].count(y))continue;
					if(vis[x])break;
					for(int k=1;k<=up;k++){
						if(vis[k]||x==k||y==k)continue;
						if(um[x].count(k)&&um[y].count(k)){
							ans.push_back({x,y,k});cnt++;
							vis[x]=vis[y]=vis[k]=1;
							break;
						}
					}
					if(cnt==n)break;
				}
				if(cnt==n)break;
			}
		}
		for(auto p:ans)cout<<p.u<<" "<<p.v<<" "<<p.w<<"\n";
	}
	return 0;
}