POJ1975[Median Weight Bead]

用Floyd求出可以确定的所有轻重关系,然后如果某个珠子有不小于(n+1)/2个珠子比它重则它不可能是中间的,如果某个珠子有不小于(n+1)/2个珠子比它轻则它不可能是中间的。


最后,Floyd也是动态规划。


CODE:


/*


AUTHOR: Su Jiao


DATE: 2010-7-22


DESCRIPTION:


动态规划 乱做


http://acm.pku.edu.cn/JudgeOnline/problem?id=1975


*/


#include <stdio.h>


#include <string.h>


 


const int MAXN=128;


int t,N,M,a,b;


int G[MAXN][MAXN];


int H[MAXN][MAXN];


 


int main()


{


    scanf(“%d”,&t);


    for (int tt=0;tt<t;tt++)


    {


        scanf(“%d%d”,&N,&M);


        memset(G,0,sizeof(G)),memset(H,0,sizeof(H));


        for (int i=0;i<M;i++)


            scanf(“%d%d”,&a,&b),G[–a][–b]=1,H[b][a]=1;


        for (int k=0;k<N;k++)


            for (int i=0;i<N;i++)


                for (int j=0;j<N;j++)


                {


                    if (G[i][k]&&G[k][j])


                       G[i][j]=1;


                    if (H[i][k]&&H[k][j])


                       H[i][j]=1;


                }


        int answer=0;


        for (int i=0;i<N;i++)


        {


            int heavier=0;


            for (int j=0;j<N;j++)


                if (G[j][i]) heavier++;


            int lighter=0;


            for (int j=0;j<N;j++)


                if (H[j][i]) lighter++;


            if (heavier>=((N+1)>>1)||lighter>=((N+1)>>1)) answer++;


        }


        printf(“%d\n”,answer);


    }


}