题意：
给n颗豆和m个重量关系，要求有几个豆不可能是重量排在第n/2个的。
分析：
在原图和他的逆图上两次floyd算出对每颗豆有多少豆比它重和比它轻。
代码：
//poj 1975
//sep9
#include <iostream>
#include <vector>
using namespace std;
const int maxN=1024;int vis[maxN];
int heavier[maxN],lighter[maxN],g[maxN][maxN],ng[maxN][maxN];
int n,m;int main()
{int i,j,k,cases;scanf("%d",&cases);while(cases--){scanf("%d%d",&n,&m);memset(g,0,sizeof(g));memset(ng,0,sizeof(ng));while(m--){int a,b;scanf("%d%d",&a,&b);g[a][b]=1;ng[b][a]=1;} memset(heavier,0,sizeof(heavier));memset(lighter,0,sizeof(lighter));for(k=1;k<=n;++k)for(i=1;i<=n;++i)for(j=1;j<=n;++j)if(g[i][k]==1&&g[k][j]==1)g[i][j]=1;for(k=1;k<=n;++k)for(i=1;i<=n;++i)for(j=1;j<=n;++j)if(ng[i][k]==1&&ng[k][j]==1)ng[i][j]=1; for(i=1;i<=n;++i){heavier[i]=0;for(j=1;j<=n;++j)heavier[i]+=g[i][j];} for(i=1;i<=n;++i){lighter[i]=0;for(j=1;j<=n;++j)lighter[i]+=ng[i][j];}int ans=0;for(i=1;i<=n;++i)if(heavier[i]>n/2||lighter[i]>n/2)++ans;printf("%d\n",ans);}return 0;
}