题目大意

给你一个无向图,图上每个点要么标记为高要么标记为低,求最多有多少组三元组[X,Y,Z]使得点X,Z是标记为高的,Y是标记为低的,X-Y,Y-Z之间都有边相连。

传送门

数据范围:

多组数据,数据组数$T\leq20$
点数$N\leq30$


这道题听GXZLegendDalao说本质上是一道NP问题。
这道题我是想不出来的,但是算法竟然是惊人的随机化

求出两个序列$Q_h$和$Q_l$,分别表示高点和低点集合。每次随机化先将它们随机打乱(random_shuffle() from <algorithm>),之后贪心匹配,每次找到一个低点,找到两个最靠前的高点和它搭配,最后更新一下答案,输出就可以了。

不得不叹服这道题随机化的大胆和隐蔽,真的是太强了QwQ
GXZ太强啦%%%

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,k,u,v,inx,cnt,ans,ret,qh[50],ql[50],toth,totl,choice[50],t;
bool dis[50][50],high[50],use[50];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        memset(dis,false,sizeof dis);
        memset(high,false,sizeof high);
        memset(use,false,sizeof use);
        memset(choice,0,sizeof choice);
        memset(qh,0,sizeof qh);
        memset(ql,0,sizeof ql);
        cnt=ans=ret=toth=totl=0;
        scanf("%d%d%d",&n,&m,&k);
        while(m--) scanf("%d%d",&u,&v),dis[u][v]=dis[v][u]=true;
        for(int i=1;i<=k;++i) scanf("%d",&inx),high[inx]=true;
        for(int i=1;i<=n;i++)
        {
            if(high[i]) qh[++toth]=i;
            else ql[++totl]=i;
        }
        for(int shuffletime=0;shuffletime<=10000;++shuffletime)
        {
            memset(use,0,sizeof use);
            random_shuffle(qh+1,qh+toth+1);
            random_shuffle(ql+1,ql+totl+1);
            ans=0;
            for(int i=1;i<=totl;++i)
            {
                cnt=0;
                for(int j=1;j<=toth;++j)
                    if(!use[qh[j]]&&dis[ql[i]][qh[j]])
                    {
                        choice[++cnt]=qh[j];
                        if(cnt==2) break;
                    }
                if(cnt!=2) continue;
                ++ans;
                use[ql[i]]=use[choice[1]]=use[choice[2]]=true;
            }
            ret=max(ans,ret);
        }
        printf("%d\n",ret);
    }
    return 0;
}