Six Degrees of Cowvin Bacon (floydDijkstra算法)

算法)"/>

Six Degrees of Cowvin Bacon (floydDijkstra算法)

Six Degrees of Cowvin Bacon

题意：牛们最近在拍电影，所以他们准备去玩一个游戏——“六度分割”的变体。 游戏是这样进行的：每个牛离自己的距离是0度，如果两个不同的牛同时出现在一个电影里，那么他们之间的距离为1度，如果两只牛从未一起工作，但它们都与第三只牛一起工作，那么他们之间的距离为2度。 这N（2<=N<=300）头牛对找出那只牛与所有牛之间的平均距离最短感兴趣。当然，不算上他自己。这些牛拍了M（1<=M<=10000）部电影，并且保证每两个牛之间都有一定的关系。求那一头牛与其它牛距离的平均值最小值，把它乘100输出。

思路：求任意两点间最短距离，典型floyd，注意一下输出的时候取下整数就行了。

#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
int const N=1e3+5;
long long INF=0x3f3f3f;
int mp[N][N],g[N];
int n,m;
void floyd()
{for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(mp[i][j]>mp[i][k]+mp[k][j])mp[i][j]=mp[i][k]+mp[k][j];}}}
}
int main()
{std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);while(cin>>n>>m){memset(mp,INF,sizeof(mp));for(int i=1;i<=m;i++){int t;cin>>t;for(int i=1;i<=t;i++)cin>>g[i];for(int j=1;j<t;j++){for(int k=j+1;k<=t;k++){mp[g[j]][g[k]]=mp[g[k]][g[j]]=1;}}}floyd();int minn=INF;for(int i=1;i<=n;i++){ int res=0;for(int j=1;j<=n;j++){if(i!=j){res+=mp[i][j];}}if(res<minn){minn=res;}}cout<<minn*100/(n-1)<<endl;}return 0;
}

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f
int map[310][310],dis[310];
int a[310];
int n;void dijkstra(int x)
{int visit[310];int i,j,min,next=0;memset(visit,0,sizeof(visit));for(i=1;i<=n;++i){dis[i]=map[x][i];}visit[x]=1;for(i=2;i<=n;++i){min=INF;for(j=1;j<=n;++j){if(!visit[j]&&min>dis[j]){next=j;min=dis[j];}}visit[next]=1;for(j=1;j<=n;++j){if(!visit[j]&&dis[j]>dis[next]+map[next][j])dis[j]=dis[next]+map[next][j];}}
}int main()
{int m,i,num,j;while(scanf("%d%d",&n,&m)!=EOF){for(i=1;i<=n;++i){for(j=1;j<=n;++j){if(i==j)map[i][j]=0;elsemap[i][j]=map[j][i]=INF;//初始化一定要为极大值 }}while(m--){scanf("%d",&num);for(i=0;i<num;++i)scanf("%d",&a[i]);for(i=0;i<num;++i){for(j=0;j<num;++j){if(a[i]!=a[j])map[a[i]][a[j]]=map[a[j]][a[i]]=1;}} }double ans=INF;for(i=1;i<=n;++i)//枚举每一头牛 {double sum=0;dijkstra(i);for(j=1;j<=n;++j)//记录到其他牛的度数之和 {if(i!=j)sum+=dis[j];}ans=min(ans,sum*1.0/(n-1));}printf("%d\n",(int)(ans*100));}return 0;
}