Six Degrees of Cowvin Bacon
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 6744 | Accepted: 3139 |
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.
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.
* 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 .]
Source
题意稍微有点难理解，就是如果两头牛出现在同一个电影里（同一行），他们的分离度是1，如果不在一行，就要通过间接方式，比方说AB在同一场，BC在同一场，那么AC分离度就是2，以此类推，A和A分离度是0。求一头和其他牛分离度最低的牛，输出这n-1个和的平均数，然后把结果乘100。（最好是先乘100再除，免得各种转换数据类型，因为题目要求输出int类型）。
思路就是floyd（因为最多300头牛）。
//#include<bits/stdc++.h> #include<cstdio> #include<queue> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<cmath> #include<iostream> using namespace std; #define maxn 305 #define INF 99999999 typedef pair<int,int> pii; vector<pii> e[maxn]; int d[maxn],vis[maxn],mp[maxn][maxn]; int n,m; void init() { for(int i=1; i<maxn; i++) { for(int j=1; j<maxn; j++) { if(i==j) mp[i][j]=0; else mp[i][j]=INF; } } } void floyd() { for(int k=1; k<=n; k++) for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]); } int main() { init(); scanf("%d %d",&n,&m); while(m--) { int t,a[maxn]; scanf("%d",&t); for(int i=0; i<t; i++) scanf("%d",&a[i]); for(int i=0; i<t; i++) for(int j=i+1; j<t; j++) { mp[a[i]][a[j]]=mp[a[j]][a[i]]=1; } } floyd(); int ans=INF; for(int i=1; i<=n; i++) { int sum=0; for(int j=1; j<=n; j++) { sum+=mp[i][j]; } ans=min(sum,ans); } int ass=ans*100/(n-1); printf("%d ",ass); return 0; }