题解：P11433 [COCI 2024/2025 #2] 三角 / Trokuti

· · 题解

前言：很好的题，校内选拔 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;
}