ShortestPath:Six Degrees of Cowvin Bacon(POJ 2139)

　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　牛与电影

　　题目大意：就是一群牛，又在玩游戏了（怎么你们经常玩游戏），这个游戏规则如下，把牛拆分成一个一个组，并且定义一个“度”，规定在一个组的牛与他自己的度为0，与其他牛的度为1，不同组的牛不存在度，但是如果牛与牛之间有联系，那么度就会想加，这一题所有的牛都会与其他所有的牛有联系，问你哪只牛与其他牛的度的总数最少，求这个总数的平均值。

　　那么这一题貌似把牛拆分成一个一个的区间，但是我们仔细想一下，其实啊这个组是不重要的，他只是影响了牛与牛之间有没有直接相连，其实仔细读下来我们直接建图就可以了，每一次一个组的信息我们都把组内的牛建立联系就行了

　　现在要求所有牛的最短距离，那么就是用Floyd算法了，很简单的代码

　　

#include <iostream>
#include <functional>
#include <algorithm>
#define MAX_N 301

using namespace std;

static int Gragh[MAX_N][MAX_N];
static int Dist[MAX_N][MAX_N];
static int tmp[MAX_N];

void Create_Gragh(const int);
void Search(const int);

int main(void)
{
    int Movie_sum, cow_sum, in_movie_sum;
    while (~scanf("%d%d", &cow_sum, &Movie_sum))
    {
        memset(Gragh, 0, sizeof(Gragh));
        for (int i = 0; i < Movie_sum; i++)
        {
            scanf("%d", &in_movie_sum);
            for (int j = 0; j < in_movie_sum; j++)
                scanf("%d", &tmp[j]);
            Create_Gragh(in_movie_sum);
        }
        Search(cow_sum);
    }
    return 0;

}

void Create_Gragh(const int in_movie_sum)
{
    for (int i = 0; i < in_movie_sum; i++)
    {
        for (int j = i + 1; j < in_movie_sum; j++)
        {
            Gragh[tmp[i]][tmp[j]] = 1;
            Gragh[tmp[j]][tmp[i]] = 1;
        }
    }
}

void Search(const int cow_sum)//Floyd算法，dp数组
{
    int min_sum = INT_MAX, sum;
    for (int i = 1; i <= cow_sum; i++)//初始化
    {
        for (int j = 1; j <= cow_sum; j++)
        {
            if (i == j) Dist[i][j] = 0;
            else if (Gragh[i][j] == 1) Dist[i][j] = 1;
            else Dist[i][j] = MAX_N + 1;
        }
    }
    for (int k = 1; k <= cow_sum; k++)//最短寻路
    {
        for (int i = 1; i <= cow_sum; i++)
            for (int j = 1; j <= cow_sum; j++)
            {
                if (i == j) continue;
                Dist[i][j] = min(Dist[i][j], Dist[i][k] + Dist[k][j]);
            }
    }
    for (int i = 1; i <= cow_sum; i++)//和其他点都有关系，我们找到那个最小平均值即可
    {
        sum = 0;
        for (int j = 1; j <= cow_sum; j++)
            sum += Dist[i][j];
        min_sum = sum < min_sum ? sum : min_sum;
    }
    printf("%d\n", min_sum * 100 / (cow_sum - 1));
}