【题目链接】
ybt 1384:珍珠(bead)
【题目考点】
1. 图论:floyd 求传递闭包
传递闭包:二维数组e,e[i][j]
表示顶点i到顶点j是否有路径。
【解题思路】
这是个有向图。每颗珍珠是一个顶点,初始情况下,如果i比j重,那么i到j有一条弧。
设布尔类型数组e,为该图的传递闭包,即e[i][j]
表示i是否比j重。
先输入已知的相对重量关系,如果输入了x,y,那么x比y重,将e[x][y]
设为1。
而后在e数组上使用floyd算法求传递闭包。k, i, j三重循环,如果i到j的重量关系还没确定(e[i][j]==0
),但是i比k重,k比j重,那么一定有i比j重。e[i][0]
记录比i轻的珍珠的数量,e[0][j]
记录比j重的珍珠的数量。遍历传递闭包e,如果e[i][j]
为真,即i比j重,那么比i轻的珍珠的数量增加1,比j重的珍珠数量增加1。
已知n是奇数,那么n/2(n整除2)的结果等于(n-1)/2。文章来源:https://www.toymoban.com/news/detail-821388.html
- 如果比i重的珍珠数量大于n/2,超过了一半,那么i的重量一定不是中间重量
- 如果比i轻的珍珠数量大于n/2,超过了一半,那么i的重量也一定不是中间重量
统计不可能是中间重量的珍珠的数量,输出结果。文章来源地址https://www.toymoban.com/news/detail-821388.html
【题解代码】
解法1:floyd求传递闭包
#include<bits/stdc++.h>
using namespace std;
#define N 105
int n, m, e[N][N], ct;//n:顶点数 m:边数 e[i][j]:输入数据中i比j重
int main()
{
int x, y;
cin >> n >> m;
for(int i = 1; i <= m; ++i)
{
cin >> x >> y;
e[x][y] = 1;
}
for(int k = 1; k <= n; ++k)
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
if(e[i][j] == 0 && e[i][k] && e[k][j])
e[i][j] = 1;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
if(e[i][j])
{
e[i][0]++;//e[i][0]:比i轻的数量
e[0][j]++;//e[0][j]:比j重的数量
}
for(int i = 1; i <= n; ++i)
if(e[i][0] > n/2 || e[0][i] > n/2)
ct++;
cout << ct;
return 0;
}
到了这里,关于信息学奥赛一本通 1384:珍珠(bead)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!