POJ 3660 （Floyd判断传递闭包）

题目：输入n头牛，m个关系。接下来m行每行两个int数a，b，代表a可以打败b

问：能确定多少头牛的排名

思路：floyd算法可以判断传递闭包问题（通过传递性推导出尽量多的元素之间的关系叫做传递闭包），模板题

#include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <string> #include <map> #include <iomanip> #include <algorithm> #include <queue> #include <stack> #include <set> #include <vector> //const int maxn = 1e5+5; #define ll long long ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} //const int inf = 0x6fffffff; #define MAX INT_MAX #define FOR(i,a,b) for( int i = a;i <= b;++i) #define bug cout<<"--------------"<<endl using namespace std; bool d[310][310]; int n,m,ans; int main() { ios::sync_with_stdio(false); cin>>n>>m; FOR(i,1,n) d[i][i] = 1; FOR(i,1,m) { int x,y,z; cin>>x>>y; d[x][y] = 1; } FOR(k,1,n) FOR(i,1,n) FOR(j,1,n) d[i][j] |= d[i][k] & d[k][j]; for(int i=1 ; i<=n;++i) { int du = 0; for(int j=1;j<=n;++j) { if(i == j) continue; if(d[i][j] == 1 || d[j][i] == 1) du++; } if(du == n-1) ans++; } cout<<ans<<endl; }

 

转载于:https://www.cnblogs.com/jrfr/p/11370913.html

相关资源：JAVA上百实例源码以及开源项目