| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
c++#include<iostream>
using namespace std;
const int maxn=307;
const int INF=1<<29;
int G[maxn][maxn];
int cow[maxn];
void floyd(int n){
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
G[i][j]=min(G[i][j],G[i][k]+G[k][j]);
}
int main()
{
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)G[i][j]=(i==j)?0:INF;
for(int i=1;i<=m;++i){
int k;scanf("%d",&k);
for(int j=0;j<k;++j){
scanf("%d",&cow[j]);
}
for(int j=0;j<k;++j)
for(int l=j+1;l<k;++l)
G[cow[j]][cow[l]]=1,G[cow[l]][cow[j]]=1;
}
floyd(n);
long long ans=INF;
for(int i=1;i<=n;++i)
{
long long sum=0;
for(int j=1;j<=n;++j)
if(i!=j)sum+=G[i][j];
ans=min(ans,sum);
}
cout<<(ans*100/(n-1))<<endl;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator