本文主要是介绍CF#318 (Div. 2)B. Bear and Three Musketeers 暴力 复杂度分析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
分析:暴力求解,,关键是分析出复杂度n^2+m*n,而不是看到三层循环就n^3,#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
#define MM(a) memset(a,0,sizeof(a))
typedef long long ll;
typedef unsigned long long ULL;
const int mod = 1000000007;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f;
const int big=50000;
int max(int a,int b) {return a>b?a:b;};
int min(int a,int b) {return a<b?a:b;};
int flag[4005][4005],d[4005];
int main()
{
int n,m,u,v;
while(~scanf("%d %d",&n,&m))
{
memset(flag,0,sizeof(flag));
memset(d,0,sizeof(d));
for(int i=1;i<=m;i++)
{
scanf("%d %d",&u,&v);
flag[u][v]=flag[v][u]=1;
d[u]++;d[v]++;
}
int ans=inf;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(flag[i][j])
for(int k=j+1;k<=n;k++)
if(flag[i][k]&&flag[k][j])
ans=min(ans,d[i]+d[j]+d[k]-6);
printf("%d\n",ans==inf?-1:ans);
}
return 0;
}
这篇关于CF#318 (Div. 2)B. Bear and Three Musketeers 暴力 复杂度分析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!