【題目鏈接】
ybt 1384：珍珠(bead)
【題目考點(diǎn)】
1. 圖論：floyd 求傳遞閉包
傳遞閉包：二維數(shù)組e，e[i][j]表示頂點(diǎn)i到頂點(diǎn)j是否有路徑。
【解題思路】
這是個(gè)有向圖。每顆珍珠是一個(gè)頂點(diǎn)，初始情況下，如果i比j重，那么i到j(luò)有一條弧。
設(shè)布爾類型數(shù)組e，為該圖的傳遞閉包，即e[i][j]表示i是否比j重。
先輸入已知的相對(duì)重量關(guān)系，如果輸入了x，y，那么x比y重，將e[x][y]設(shè)為1。
而后在e數(shù)組上使用floyd算法求傳遞閉包。k, i, j三重循環(huán)，如果i到j(luò)的重量關(guān)系還沒確定(e[i][j]==0)，但是i比k重，k比j重，那么一定有i比j重。e[i][0]記錄比i輕的珍珠的數(shù)量，e[0][j]記錄比j重的珍珠的數(shù)量。遍歷傳遞閉包e，如果e[i][j]為真，即i比j重，那么比i輕的珍珠的數(shù)量增加1，比j重的珍珠數(shù)量增加1。
已知n是奇數(shù)，那么n/2(n整除2)的結(jié)果等于(n-1)/2。文章來源：http://www.zghlxwxcb.cn/news/detail-821388.html
- 如果比i重的珍珠數(shù)量大于n/2，超過了一半，那么i的重量一定不是中間重量
- 如果比i輕的珍珠數(shù)量大于n/2，超過了一半，那么i的重量也一定不是中間重量
統(tǒng)計(jì)不可能是中間重量的珍珠的數(shù)量，輸出結(jié)果。文章來源地址http://www.zghlxwxcb.cn/news/detail-821388.html
【題解代碼】
解法1：floyd求傳遞閉包
#include<bits/stdc++.h>
using namespace std;
#define N 105
int n, m, e[N][N], ct;//n：頂點(diǎn)數(shù) m：邊數(shù) e[i][j]：輸入數(shù)據(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輕的數(shù)量
e[0][j]++;//e[0][j]：比j重的數(shù)量
}
for(int i = 1; i <= n; ++i)
if(e[i][0] > n/2 || e[0][i] > n/2)
ct++;
cout << ct;
return 0;
}
到了這里，關(guān)于信息學(xué)奧賽一本通 1384：珍珠(bead)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
