B. Bear and Three Musketeers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Do you know a story about the three musketeers? Anyway, you will learn about its origins now.
Richelimakieu is a cardinal in the city of Bearis. He is tired of dealing with crime by himself. He needs three brave warriors to help him to fight against bad guys.
There are n warriors. Richelimakieu wants to choose three of them to become musketeers but it's not that easy. The most important condition is that musketeers must know each other to cooperate efficiently. And they
shouldn't be too well known because they could be betrayed by old friends. For each musketeer hisrecognition is the number of warriors he knows, excluding other two musketeers.
Help Richelimakieu! Find if it is possible to choose three musketeers knowing each other, and what is minimum possible sum of their recognitions.
Input
The first line contains two space-separated integers, n andm (3 ≤ n ≤ 4000,0 ≤ m ≤ 4000) — respectively
number of warriors and number of pairs of warriors knowing each other.
i-th of the following
m lines contains two space-separated integers
ai and
bi (1 ≤ ai, bi ≤ n,ai ≠ bi).
Warriorsai andbi know each other. Each pair of warriors will be listed at most once.
Output
If Richelimakieu can choose three musketeers, print the minimum possible sum of their recognitions. Otherwise, print "-1" (without the quotes).
Sample test(s)
Input
5 6 1 2 1 3 2 3 2 4 3 4 4 5
Output
2
Input
7 4 2 1 3 6 5 1 1 7
Output
-1
题目大意：
给你n个人和m个关系，(a,b)表示a和b认识，现在这个人想雇佣其中3个人，
1： 这3个人必须相互认识
2： 这3个人的识别度的总和最小（一个人的识别度为：除了另外两人认识的人的数，三个人的识别度相加最小）
解题思路：
类似于Floyd算法，但是不完全是，这其实是一个图。。。
上代码：
/*
2015 - 09 - 14 晚上
Author: ITAK
Motto:
今日的我要超越昨日的我，明日的我要胜过今日的我，
以创作出更好的代码为目标，不断地超越自己。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 4e3+5;
const double eps = 1e-7;
int x[maxn], y[maxn];
int arr[maxn];
bool g[maxn][maxn];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=0; i<m; i++)
{
scanf("%d%d",&x[i],&y[i]);
g[x[i]][y[i]] = g[y[i]][x[i]] = 1;
arr[x[i]]++;
arr[y[i]]++;
}
bool ok= false;
int Min = 999999;
for(int i=0; i<m; i++)
for(int j=1; j<=n; j++)
if(g[x[i]][j] && g[j][y[i]] )
if(Min > arr[x[i]]+arr[j]+arr[y[i]])
{
Min = arr[x[i]]+arr[j]+arr[y[i]];
ok = true;
}
if (!ok)
puts("-1");
else
printf("%d\n",Min-6);
return 0;
}
/*
南山南 (Live) - 张磊
词：马頔
曲：马頔
你在南方的艳阳里大雪纷飞
我在北方的寒夜里四季如春
如果天黑之前来得及
我要忘了你的眼睛
穷极一生 做不完一场梦
他不再和谁谈论相逢的孤岛
因为心里早已荒无人烟
他的心里再装不下一个家
做一个只对自己说谎的哑巴
他说你任何为人称道的美丽
不及他第一次遇见你
时光苟延残喘 无可奈何
如果所有土地连在一起
走上一生 只为拥抱你
喝醉了他的梦 晚安
你在南方的艳阳里大雪纷飞
我在北方的寒夜里四季如春
如果天黑之前来得及
我要忘了你的眼睛
穷极一生 做不完一场梦
大梦初醒 荒唐了一生
南山南 北秋悲
南山有谷堆
南风喃 北海北
北海有墓碑
南山南 北秋悲
南山有谷堆
南风喃 北秋悲
北海有墓碑
北海有墓碑
*/