Cow Contest（Warshall算法+结论）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Cow Contest（Warshall算法+结论），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含809字，纯文字阅读大概需要2分钟。

内容图文

这道题终于把离散数学学到的Warshall算法用上了，好开心；所以比赛是最好的知识使用场；
这道题根据题意可以知道，A wins B ，Bwins C就可以知道A wins C所以这很明显就是传递闭包，然后最后去求位置确定的个数，那么得到确定位置的个数那么就必须知道这点：如果A 赢了x头牛，输给了y头牛，那么如果A的位置确定就应该有x+y==n-1；
所以最后利用Warshall算法求出传递闭包然后各自扫一遍就出来答案了：

#include<bits/stdc++.h>
using namespace std;
int R[200][200];
int main(){
	int n,m,a,b;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		  cin>>a>>b;
		  R[a][b]=1;
	}
	for(int i=1;i<=n;i++){//warshall算法
		  for(int k=1;k<=n;k++){
		  	  if(R[k][i]){
		  	  	  for(int j=1;j<=n;j++){
		  	  	  	   if(R[i][j]) R[k][j]=1;
					  }
				}
		  }
	}
	int temp;
	int ans=0;
	for(int i=1;i<=n;i++){
		 temp=0;
		  for(int j=1;j<=n;j++){
		  	  if(R[i][j])temp++;
		  }
		  for(int k=1;k<=n;k++){
		  	  if(R[k][i])temp++;
		  }
		  if(temp==n-1)ans++;
	}
	printf("%d\n",ans);
	
	 return 0;
}

内容总结

以上是互联网集市为您收集整理的Cow Contest（Warshall算法+结论）全部内容，希望文章能够帮你解决Cow Contest（Warshall算法+结论）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---