poj 2139 flord水题

读懂题意就简单了
#include<stdio.h>

#define inf 999999999

#define N 310

int f[N];

int map[N][N];

int main() {

    int n,m,i,j,k,a,b,max,ans;

    while(scanf("%d%d",&n,&m)!=EOF) {

     for(i=1;i<=n;i++)

     for(j=1;j<=n;j++)

     map[i][j]=inf;

     while(m--) {

        scanf("%d",&k);

        for(j=1;j<=k;j++)

            scanf("%d",&f[j]);

        for(j=1;j<=k;j++)

            for(a=j+1;a<=k;a++)

            map[f[j]][f[a]]=map[f[a]][f[j]]=1;

     }

     for(k=1;k<=n;k++)

     for(i=1;i<=n;i++)

        for(j=1;j<=n;j++) {

                if(i==j||i==k)continue;

        if(map[i][j]>map[i][k]+map[k][j])

        map[i][j]=map[i][k]+map[k][j];

        }

        max=inf;

     for(i=1;i<=n;i++) {

            ans=0;

        for(j=1;j<=n;j++)

        if(i!=j)

           ans+=map[i][j];

     if(max>ans)

     max=ans;

     }

     printf("%d\n",max*100/(n-1));

    }

return 0;

}
巴特西

poj 2139 flord水题

最新文章

热门文章
