Codeforces Round #318 [RussianCodeCup Thanks-Round] (Div. 2)

B.Bear and Three Musketeers

$\mathtt{Difficulty}$=$\mathtt{1500}$
使用暴力可以通过本题。
我们考虑暴力枚举 $3$ 个点，
条件为两两之间都有连边，
然后取这 $3$ 个点的度数之和的最小值。
因为不包括这 $3$ 个点本身，
所以最终答案还要 $-6$。
但是，
这样写会得到 $\texttt{TLE}$，
不难想到一个基础的剪枝，
就是如果选的 $2$ 个点已经没有连边，
就直接 break 掉。
代码就不难写出了。

#include<bits/stdc++.h>
#define BetterIO ios::sync_with_stdio(false)
using namespace std;
int N,M,Deg[4001];
bool Map[4001][4001];
int main(void)
{
	BetterIO;
	register int i,j,k;cin>>N>>M;
	for(i=1;i<=M;i++)
	{
		register int U,V;cin>>U>>V;
		Map[U][V]=Map[V][U]=true,Deg[U]++,Deg[V]++;
	}
	register int Ret(INT_MAX);
	for(i=1;i<=N;i++)for(j=i+1;j<=N;j++)if(Map[i][j])for(k=j+1;k<=N;k++)if(Map[i][j]&&Map[i][k]&&Map[j][k])Ret=min(Ret,Deg[i]+Deg[j]+Deg[k]);
	if(Ret==INT_MAX)Ret=5;
	cout<<Ret-6<<endl;
	return 0;
}