POJ 3660 Cow Contest(求图的传递性)

题意:

给定n头牛, 然后有m个比较, 求出有多少头牛能确定自己的排名。

分析:

假设有一头牛a, 有ki头牛强于自己, kj头牛弱于自己, ki + kj == n-1时, 那么这头牛的排名就确定了。

对于每个比较建一条有向边

求出a点可达哪些点, 哪些点可达a点即可

#include<cstdio>
#include<string>
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#define rep(i,a,b) for(int i = a; i < b; i++)
#define _rep(i,a,b) for(int i = a; i <= b; i++)
using namespace std;
const int maxn = ;
const int inf = 1e9;
int G[maxn][maxn];
int n , m;
int main()
{
while(~scanf("%d %d", &n, &m)){
rep(i,,maxn) rep(j,,maxn) G[i][j] = ; rep(i,,m) {
int u, v;
scanf("%d %d", &u, &v);
G[u][v] = ;
}
for(int k = ; k <= n; k++){
for(int i = ; i <= n; i++){
for(int j = ; j <= n; j++){
if(G[i][j] == ) G[i][j] = G[i][k] && G[k][j]; //只有当 G[i][k] && G[k][j] 都有路时, G[i][j]才算联通
}
}
}
int ans = ;
_rep(i,,n){
int cnt = ;
_rep(j,,n){
if(G[i][j]) cnt++;
if(G[j][i]) cnt++;
}
if(cnt == n - ) ans++;
}
printf("%d\n", ans);
}
return ;
}
上一篇:hdu 6082 度度熊与邪恶大魔王(2017"百度之星"程序设计大赛 - 资格赛 )


下一篇:[SinGuLaRiTy] 2017 百度之星程序设计大赛-资格赛