Cow Contest(Warshall算法+结论)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Cow Contest(Warshall算法+结论),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含809字,纯文字阅读大概需要2分钟。
内容图文
![Cow Contest(Warshall算法+结论)](/upload/InfoBanner/zyjiaocheng/741/d1705201ef174c24bdd5e278a7dd7ce5.jpg)
这道题终于把离散数学学到的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 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。