題目描述：

眾所周知，TT 有一只魔法貓。這一天，TT 正在專心致志地玩《貓和老鼠》游戲，然而比賽還沒開始，聰明的魔法貓便告訴了 TT 比賽的最終結果。TT 非常詫異，不僅詫異于他的小貓咪居然會說話，更詫異于這可愛的小不點為何有如此魔力？魔法貓告訴 TT，它其實擁有一張游戲勝負表，上面有 N 個人以及 M 個勝負關系，每個勝負關系為 A B，表示 A 能勝過 B，且勝負關系具有傳遞性。即 A 勝過 B，B 勝過 C，則 A 也能勝過 C。TT 不相信他的小貓咪什么比賽都能預測，因此他想知道有多少對選手的勝負無法預先得知，你能幫幫他嗎？

input：

第一行給出數據組數。每組數據第一行給出 N 和 M（N , M <= 500）。接下來 M 行，每行給出 A B，表示 A 可以勝過 B。

output：

對于每一組數據，判斷有多少場比賽的勝負不能預先得知。注意 (a, b) 與 (b, a) 等價，即每一個二元組只被計算一次。

思路：

抽象成圖論問題，n個點表示n個選手，給出m對關系，每對關系輸入a,b，表示選手a能戰勝選手b，在圖中表現為a到b有一條有向邊，邊權為1。由于勝負關系具有傳遞性，A勝B，B勝C，則A勝C。考慮floyed算法，三層循環，最外層枚舉k，表示中間點即前面說的點B。第二層枚舉i表示起始點，即前面說的點A，最內層枚舉j表示終點，即前面說的C，若a[i][k]==1,且a[k][j]==1，則更新a[i][j]=1。

由于當a[i][k]或者a[k][j]任意一個為0時表示勝負關系未知，即使循環也是無效的，因此可剪枝來優化算法。

最終枚舉矩陣的右上角（不包括對角線元素），統計答案。

#include<iostream> #include<cstring> using namespace std; int n,m,ans,a[510][510]; int main() {int T,x,y;cin>>T;while(T--){cin>>n>>m;ans=0;memset(a,0,sizeof(a));for(int i=1;i<=m;i++){cin>>x>>y;a[x][y]=1;}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)if(a[i][k])//剪枝 for(int j=1;j<=n;j++)if(a[k][j]){a[i][j]=1;}for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)//雖然枚舉右上角，但還是要考慮左下角的對稱元素。 if(!a[i][j]&&!a[j][i]) ans++;cout<<ans<<endl;} }

?

總結

以上是生活随笔為你收集整理的程序设计思维与实践 Week7 作业 A TT的魔法猫的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。