題目：

Description
The cows have been making movies lately, so they are ready to play a variant of the famous game "Six Degrees of Kevin Bacon". The game works like this: each cow is considered to be zero degrees of separation (degrees) away from herself. If two distinct cows have been in a movie together, each is considered to be one 'degree' away from the other. If a two cows have never worked together but have both worked with a third cow, they are considered to be two 'degrees' away from each other (counted as: one degree to the cow they've worked with and one more to the other cow). This scales to the general case. The N (2 <= N <= 300) cows are interested in figuring out which cow has the smallest average degree of separation from all the other cows. excluding herself of course. The cows have made M (1 <= M <= 10000) movies and it is guaranteed that some relationship path exists between every pair of cows.
Input

• Line 1: Two space-separated integers: N and M * Lines 2..M+1: Each input line contains a set of two or more space-separated integers that describes the cows appearing in a single movie. The first integer is the number of cows participating in the described movie, (e.g., Mi); the subsequent Mi integers tell which cows were.
  Output
• Line 1: A single integer that is 100 times the shortest mean degree of separation of any of the cows.
  Sample Input
  4 2
  3 1 2 3
  2 3 4
  Sample Output
  100
  Hint
  [Cow 3 has worked with all the other cows and thus has degrees of separation: 1, 1, and 1 -- a mean of 1.00 .]

題目是說N頭牛去拍M部電影，每部電影都有相應(yīng)的牛當演員。
同一部電影的演員兩兩有關(guān)系，不同的電影中的演員沒有關(guān)系（關(guān)系的權(quán)值為1）。
問題是對于每頭牛與其他牛的關(guān)系之和求出最小的并且*100再除以N-1.

此題由于N的值不是很大，因此可以用Floyd-Warshall算法解決，將任意2頭牛之間的關(guān)系求出，然后求出每頭牛與其他牛的關(guān)系總和，最后比較即可，然后進行相應(yīng)的處理。

參考代碼：

#include <iostream>
#include <algorithm>
#define N 320
#define INF 99999
using namespace std;
int d[N][N];
void cl(int n) {
    for (int i = 1;i <= n;++i) {
        for (int j = 1;j <= n;++j) {
            d[i][j] = INF;
        }
    }
    for (int i = 1;i <= n;++i) {
        d[i][i] = 0;
    }
}
void floyed(int n) {
    for (int k = 1;k <= n;++k) {
        for (int i = 1;i <= n;++i) {
            for (int j = 1;j <= n;++j) {
                d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }   
}
int minways(int n) {
    int minw = 99999;
    int w;
    for (int i = 1;i <= n;++i) {
        w = 0;
        for (int j = 1;j <= n;++j) {
            if (i != j && d[i][j] != INF) w = w + d[i][j];
            //cout << w << endl;    
        }
        //cout << w << endl;
        if (w < minw) minw = w;
    }
    return minw;
}
int average(int minw,int n) {
    int aver;
    aver = minw * 100 / (n-1);
    return aver;
} 
int main() {
    int n,m;
    while (cin >> n >> m) {
        cl(n);
        int num1;
        int cows[N];
        for (int i = 1;i <= m;++i) {
            cin >> num1;
            int k = 1;
            for (int j = 1;j <= num1;++j) {
                cin >> cows[k];
                k++;
            }
            for (int i1 = 1;i1 < k;++i1) {
                for (int i2 = 1;i2 < k;++i2) {
                    if (cows[i1] != cows[i2]) {
                        d[cows[i1]][cows[i2]] = 1;
                    }
                }
            }
        }
        floyed(n);
        int minw = minways(n);
        //cout << minw << endl;
        int aver = average(minw,n);
        cout << aver << endl;
    }
    return 0;
}

此題也可以用其他方法求出結(jié)果，這里就不再列出了。

話說poj里的牛真屌，又開party又拍電影，還辦學(xué)校，甚至探索蟲洞的奧秘，比我們還厲害。這年頭，不好好學(xué)習(xí)，連牛都要鄙視你。