poj 2139 Six Degrees of Cowvin Bacon-白红宇

poj 2139 Six Degrees of Cowvin Bacon

阅读量：5924 次

发布时间：2019-06-19

本文共 2670 字，大约阅读时间需要 8 分钟。

Six Degrees of Cowvin Bacon

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 5766		Accepted: 2712

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 23 1 2 32 3 4

Sample Output

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 .]

Source

/** @Author: Lyucheng* @Date:   2017-07-21 10:09:45* @Last Modified by:   Lyucheng* @Last Modified time: 2017-07-21 10:32:45*//* 题意：有n头奶牛，如果奶牛在同一部电影中工作过，那么这些奶牛就是有关系的，关系距离为1    当然也可以通过其他奶牛产生间接的关系，问你那头奶牛的与其他奶牛的平均关系距离最小 思路：建边然后最短路*/#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #define MAXN 305#define INF 10000000using namespace std;int n,m;int t;int pos[MAXN];int dp[MAXN][MAXN];void floyd(){ for(int i=1;i<=n;i++){ for(int k=1;k<=n;k++){ if(k==i) continue; for(int j=1;j<=n;j++){ if(j==i) continue; dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]); } } }}void init(){ for(int i=0;i<=n;i++){ for(int j=0;j<=n;j++){ dp[i][j]=INF; } dp[i][i]=0; }}int main(){ // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(scanf("%d%d",&n,&m)!=EOF){ init(); for(int i=0;i

转载于:https://www.cnblogs.com/wuwangchuxin0924/p/7216430.html

你可能感兴趣的文章