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

青旅半醒 2022-06-12 06:15 177阅读 0赞

Think:  
1知识点：最短路+\_Floyd()算法求传递背包数量  
2反思：学习知识要努力拓展创新

[建议参考博客1][1]  
[建议参考博客2][2]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 1e2 + 4;
    
    int n, e[N][N];
    
    void Floyd();
    
    int main(){
        int m, i, j, u, v, sum, ans;
        while(~scanf("%d %d", &n, &m)){
            ans = 0;
            memset(e, 0, sizeof(e));
            for(i = 1; i <= m; i++){
                scanf("%d %d", &u, &v);
                e[u][v] = 1;
            }
            Floyd();
            for(i = 1; i <= n; i++){
                sum = 0;
                for(j = 1; j <= n; j++){
                    if(e[i][j] || e[j][i])
                        sum++;
                }
                if(sum == n-1)
                    ans++;
            }
            printf("%d\n", ans);
        }
        return 0;
    }
    void Floyd(){
        int i, j, k;
        for(k = 1; k <= n; k++){
            for(i = 1; i <= n; i++){
                for(j = 1; j <= n; j++){
                    if(e[i][k] && e[k][j])
                        e[i][j] = 1;
                }
            }
        }
    }

[1]: http://blog.csdn.net/u012629369/article/details/24184265
[2]: http://blog.csdn.net/to_be_better/article/details/50529094

发表评论取消回复

表情：

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

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

相关阅读

相关 [kuangbin带你飞]专题四最短路练习 H - Cow Contest （floyed传递背包）

H - Cow Contest 题目链接：[https://vjudge.net/contest/66569\problem/H][https_vjudge.net_co

怼烎@/ 2023年08月17日 15:41/ 0 赞/ 112 阅读

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

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

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

相关 poj 3660 Cow Contest【floyd】

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

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

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

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

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

相关 D - Silver Cow Party——最短路_spfa()算法

Think: 1知识点：最短路\_spfa()算法 2反思：图的初始化 3思路：通过正向边spfa()求出回去的，反向边spfa()求出到达的 [建议参考题意分析

怼烎@/ 2022年06月12日 05:54/ 0 赞/ 187 阅读

相关 JavaScript与Floyd 最短路算法

背景 -------------------- NBA超级后场组合灯泡组合(Harden和CP3)休赛期来到中国玩耍，他们两人打算在四个城市进行玩耍，最后他们选择了北京

朱雀/ 2022年05月29日 06:06/ 0 赞/ 200 阅读

相关 JavaScript与Floyd最短路算法

背景 -------------------- NBA超级后场组合灯泡组合(Harden和CP3)休赛期来到中国玩耍，他们两人打算在四个城市进行玩耍，最后他们选择了北京

r囧r小猫/ 2022年05月26日 01:17/ 0 赞/ 222 阅读

相关 floyd算法----------求最短路问题

floyd算法原理：动态规划问题，核心思想就是从i到j的最短路问题，但是如果存在k,使得i->k->j的距离小于i->j的距离就更新dp\[i\]\[j\]值先建立一个

小鱼儿/ 2022年04月14日 03:19/ 0 赞/ 254 阅读

相关最短路之——弗洛伊德算法（floyd）

来源： https://blog.csdn.net/riba2534/article/details/54562440 ![20170115155852215][] 我们要

电玩女神/ 2021年12月07日 14:15/ 0 赞/ 342 阅读

相关 poj3268 Silver Cow Party（最短路）

非常感谢kuangbin专题啊，这道题一开始模拟邻接表做的，反向边不好处理，邻接矩阵的话舒服多了。题意：给n头牛和m条有向边，每头牛1~n编号，求所有牛中到x编号去的最短路

素颜马尾好姑娘i/ 2021年10月29日 16:22/ 0 赞/ 202 阅读