本文共 1437 字，大约阅读时间需要 4 分钟。

题目：

这一天，TT 正在专心致志地玩《猫和老鼠》游戏，然而比赛还没开始，聪明的魔法猫便告诉了 TT 比赛的最终结果。TT 非常诧异，不仅诧异于他的小猫咪居然会说话，更诧异于这可爱的小不点为何有如此魔力？

魔法猫告诉 TT，它其实拥有一张游戏胜负表，上面有 N 个人以及 M 个胜负关系，每个胜负关系为 A B，表示 A 能胜过 B，且胜负关系具有传递性。即 A 胜过 B，B 胜过 C，则 A 也能胜过 C。

TT 不相信他的小猫咪什么比赛都能预测，因此他想知道有多少对选手的胜负无法预先得知，你能帮帮他吗？

读完上面一段话，明白一个重点：N个人  M个胜负关系A→B B→C 一定有 A→C 即M是一个关系，M 满足传递闭包

Input

test data

33 31 21 32 33 21 22 34 21 23 4

output

解：这个问题解答运用了Floyd算法，Floyd算法嘛，针对本题，首先我们不妨设两条可以连通的路为e[i][j]=1,中转站k，如果e[i][k]=1,e[k][j]=1同时成立，那么i,j也是连通的，e[i][j]=1，//传递性。因为有多个参赛选手，对于每一个中间选手，就是我们说的中转站，那么本题就成为多起点，多源问题了，它只要成立，那么两地可连通，也就是我们所说的两个人胜负关系可知

Floyd算法可以参考

#include
   
    #include
    
     using namespace std;int groups,m,n,a,b,ans;//n个人，m个胜负关系,关系a，b ,ans最后答案 int dis[510][510];void floyd(){
   //经典3层循环  for(int k=1;k<=n;k++)  for(int mi=1;mi<=n;mi++)   if(dis[mi][k]==1)//明确胜负关系    for(int j=1;j<=n;j++)//求最大值的最小值      dis[mi][j]=max(dis[mi][j],dis[mi][k]&dis[k][j]); //↑为什么是max呢？因为dis[a][b] dis[b][c]说明一定有dis[a][c] //也即是说满足题意关系的传递闭包  for(int j=1;j<=n;j++)  for(int mj=j+1;mj<=n;mj++)   if(dis[j][mj]==0 && dis[mj][j]==0)//不确定关系    ans++; cout<
     
      <
      
       >groups; for(int i=1;i<=groups;i++){
     cin>>n>>m;  memset(dis,0,sizeof(dis));  ans=0;  for(int j=1;j<=m;j++){
      cin>>a>>b;   dis[a][b]=1;  }  floyd();  } return 0;}
      
     
    
   

转载地址：http://zdwzi.baihongyu.com/