题意:题目给出n,m。n代表母牛的数量,m代表接下来的行数。接下来的m行,首先给出一个x,表示x后面跟的数,也就是母牛的编号(这里从1开始,当然从0开始也一样),表示这x头母牛之间存在关系,每一个关系之间为1,当然不包括自己(也就是temp[t]==temp[j]),代表自己和自己)。最后就是使用Flody算法求解。
Flody算法的核心:
for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){e[i][j]=min(e[i][k]+e[k][j],e[i][j]);}}}
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<iomanip>
using namespace std;
const int maxx=302;
const int inf=0x3f3f3f3f;
int e[maxx][maxx];
int n,m;
void init(){for(int i=0;i<=n;i++){for(int j=0;j<=n;j++){if(i==j){e[i][j]=0;}else{e[i][j]=inf;}}}
}
void Flody(int n){for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){e[i][j]=min(e[i][k]+e[k][j],e[i][j]);}}}
}
int main(){while(scanf("%d %d",&n,&m)!=EOF){init();for(int i=1;i<=m;i++){int x;cin>>x;int temp[maxx];memset(temp,0,sizeof(temp));int k=0;for(int j=1;j<=x;j++){cin>>temp[++k];}for(int t=1;t<=x;t++){for(int j=t+1;j<=x;j++){if(temp[t]==temp[j])continue;e[temp[t]][temp[j]]=e[temp[j]][temp[t]]=1;}}}Flody(n);int timemin=inf;int id=0;for(int i=1;i<=n;i++){int tempmax=0;for(int j=1;j<=n;j++){tempmax+=e[i][j];}if(timemin>tempmax){timemin=tempmax;}}cout<<(int)timemin*100/(n-1)<<endl;}return 0;
}