首页 > 其他 > 详细

Cow Contest POJ - 3660

时间:2020-02-28 13:18:14      阅读:59      评论:0      收藏:0      [点我收藏+]

判断某个点在所有点中的位置是否是确定的(Floyd)

链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

using namespace std;
const int maxn=102;
int dis[maxn][maxn];

int ()
{
int n, m;
cin>>n>>m;
int a,b;
for(int i=1; i<=n; i++)
for(int j=1 大专栏  Cow Contest POJ - 3660; j<=n; j++)
dis[i][j]=0; //“0”为为确立关系, “1”为关系已确立;
while(m--)
{
cin>>a>>b;
dis[a][b]=1; //输入时不能加dis[b][a],关系就乱了。
}
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
{
if(k!=i&&k!=j&&i!=j)
if(dis[i][k]&&dis[k][j]) dis[i][j]=1; //不能加dis[j][i]=1,原因同上;
}
int ans=0;
for(int i=1; i<=n; i++)
{
int cnt=0;
for(int j=1; j<=n; j++)
{
if(dis[i][j]||dis[j][i]) ++cnt; //这里用或,无论是击败还是被击败,关系都是确立的;
}
if(cnt==n-1) ++ans; //只要一个点和其他所有点的关系确定了, 那这个点的位置就是确定的
}
cout<<ans<<endl;
return 0;
}

Cow Contest POJ - 3660

原文:https://www.cnblogs.com/lijianming180/p/12376437.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!