H - Cow Contest POJ - 3660——————floyd（传递闭包）

爱被打了一巴掌 2023-05-29 03:12 17阅读 0赞

[H - Cow Contest POJ - 3660][]

#include<cstdio>
    #include<cstring>
    #include<iostream>
    
    using namespace std;
    const int inf = 0x3f3f3f;
    const int maxn = 110;
    int mp[maxn][maxn];
    int c[maxn];
    int r[maxn];
    int n, m;
    
    void floyd()
    { 
        for(int k = 1;k<= n;k++)// 求传递闭包
        { 
            for(int i = 1;i <= n;i++)
            { 
                for(int j = 1;j <= n;j++)
                { 
                    if(mp[i][k]&&mp[k][j])mp[i][j] = 1;
                }
            }
        }
        
        for(int i = 1;i <= n;i++)// 求出度 和入度
        { 
            for(int j = 1;j <= n;j++)
            { 
                if(mp[i][j])
                { 
                    mp[i][0]++;// 0 存出度
                    mp[j][101]++;// 101 存入读
                }
            }
        }
    }
    
    int main()
    { 
        ios_base::sync_with_stdio(false);
        cin>>n>>m;
        memset(mp, 0, sizeof(mp));
        memset(c, 0, sizeof(c));
        memset(r, 0, sizeof(r));
        for(int i = 0;i < m;i++)
        { 
            int u, v;
            cin>>u>>v;
            mp[u][v] = 1;
        }
        floyd();
        int ans = 0;
        for(int i = 1;i <= n;i++)
        { 
            if(mp[i][0]+mp[i][101] == n-1)ans++;//如果 出度+入读 == 点的个数-1 就能确定其排名
        }
        cout<<ans;
        return 0;
    }

[H - Cow Contest POJ - 3660]: http://poj.org/problem?id=3660

发表评论取消回复

表情：

评论列表（有 0 条评论，17人围观）

还没有评论，来说两句吧...

相关阅读

相关 H - Cow Contest POJ - 3660——————floyd（传递闭包）

[H - Cow Contest POJ - 3660][] include<cstdio> include<cstring> include<ios

爱被打了一巴掌/ 2023年05月29日 03:12/ 0 赞/ 18 阅读

相关 343 排序（floyd算法求解传递闭包）

1. 问题描述：给定 n 个变量和 m 个不等式。其中 n 小于等于 26，变量分别用前 n 的大写英文字母表示。不等式之间具有传递性，即若 A > B 且 B > C，则

刺骨的言语ヽ痛彻心扉/ 2022年09月17日 03:01/ 0 赞/ 152 阅读

相关 Floyed求传递闭包 poj 3660

Floyed算法本来是求最短路的一个比较低效率的算法。介绍[http://blog.csdn.net/y990041769/article/details/8524903]

清疚/ 2022年08月25日 08:29/ 0 赞/ 162 阅读

相关 poj 3660 传递性关系 floyd更新

Cow Contest <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS<

刺骨的言语ヽ痛彻心扉/ 2022年08月10日 09:48/ 0 赞/ 32 阅读

相关 POJ 3660 Cow Contest（传递闭包floyed算法）

Description N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are participating in a pr

╰+哭是因爲堅強的太久メ/ 2022年08月09日 13:46/ 0 赞/ 149 阅读

相关 poj 3660 Cow Contest【floyd】

Cow Contest <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</

落日映苍穹つ/ 2022年08月04日 13:49/ 0 赞/ 181 阅读

相关 POJ - 3660 - Cow Contest

-------------------- 题目连接：[http://poj.org/problem?id=3660][http_poj.org_problem_id_3660

- 日理万妓/ 2022年06月12日 12:25/ 0 赞/ 216 阅读

相关 H - Cow Contest——最短路+_Floyd()算法

Think: 1知识点：最短路+\_Floyd()算法求传递背包数量 2反思：学习知识要努力拓展创新 [建议参考博客1][1] [建议参考博客2][2] 以下为

青旅半醒/ 2022年06月12日 06:15/ 0 赞/ 177 阅读

相关 poj-3660---Cow Contest

Cow Contest <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS<

我会带着你远行/ 2022年05月26日 08:14/ 0 赞/ 57 阅读

相关 Floyd传递闭包：注意三层循环的顺序

Floyd传递闭包是隔代建立联系的一种图论算法，举个例子，a可以指向b，b可以指向c，那么a就可以指向c。 Floyd传递闭包算法的时间复杂度是O(n3)，用三层循环实现，如

电玩女神/ 2022年01月29日 08:41/ 0 赞/ 206 阅读