【Floyd】牛的比赛

怼烎@ 2024-03-25 20:05 31阅读 0赞

第一次见这种，记录一下

[4244. 牛的比赛 - AcWing题库][4244. _ - AcWing]

题意：

![46863b37b5bf5d0adab12681df34bea2.png][]

思路：

考虑用Floyd

当i单向能到k，k单向能到j时，i就单向能到j，因此考虑Floyd

传递闭包的含金量！

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e2+10;
    const int mxe=2e5+10;
    
    
    int n,m,u,v;
    int dp[mxn][mxn];
    void solve(){
        cin>>n>>m;
        for(int i=1;i<=m;i++){
            cin>>u>>v;
            dp[u][v]=1;
        }
        for(int k=1;k<=n;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    dp[i][j]=dp[i][j]|(dp[i][k]&dp[k][j]);
                }
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            int cnt=0;
            for(int j=1;j<=n;j++){
                if(dp[i][j]||dp[j][i]) cnt++;
            }
            if(cnt==n-1) ans++;
        }
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[4244. _ - AcWing]: https://www.acwing.com/problem/content/4247/
[46863b37b5bf5d0adab12681df34bea2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/660662eea27a4c69935ed2495c1f5c09.png

发表评论取消回复

表情：

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

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

相关阅读

相关【Floyd】牛的比赛

第一次见这种，记录一下 [4244. 牛的比赛 - AcWing题库][4244. _ - AcWing] 题意： ![46863b37b5bf5d0adab12681d

怼烎@/ 2024年03月25日 20:05/ 0 赞/ 32 阅读

相关 Floyd算法

Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦

雨点打透心脏的1/2处/ 2023年07月17日 15:59/ 0 赞/ 125 阅读

相关 Floyd算法

Floyd算法的理解 Floyd算法是用来求两点之间的最短路径的，它的一大特点就是三循环，时间复杂度是n^3。对于Floyd算法，相信初学者大多都会有一个疑问，就是

迷南。/ 2023年07月08日 09:18/ 0 赞/ 21 阅读

相关 1125 牛的旅行（floyd算法的基础应用）

1. 问题描述：农民John的农场里有很多牧区，有的路径连接一些特定的牧区。一片所有连通的牧区称为一个牧场。但是就目前而言，你能看到至少有两个牧区不连通。现在，John想在

古城微笑少年丶/ 2022年08月28日 03:51/ 0 赞/ 11 阅读

相关奇怪的比赛

某电视台举办了低碳生活大奖赛。题目的计分规则相当奇怪：每位选手需要回答10个问题（其编号为1到10），越后面越有难度。答对的，当前分数翻倍；答错了则扣掉与题号相同的分数

亦凉/ 2022年08月08日 13:59/ 0 赞/ 167 阅读

相关 FLOYD

求出图中两顶点间的最短路径，让我们想到的是DIJIKSTRA算法，即单源最短路径的算法。那如果求所有顶点两两之间的最短路径的值，是否只要调用N次DIJIKSTRA了？当

红太狼/ 2022年08月05日 05:08/ 0 赞/ 166 阅读

相关大臣的旅费_Floyd

package 搜索; import java.util.Scanner; public class 大臣的旅费\_Floyd \{ pub

约定不等于承诺〃/ 2022年07月12日 12:14/ 0 赞/ 156 阅读

相关 WUST 1933 牛的旅行（超难理解的题意+Floyd）

1933: 牛的旅行 Time Limit: 1 Sec Memory Limit: 128 MB 64bit IO Format: %lld Submitted:

电玩女神/ 2022年06月12日 04:56/ 0 赞/ 131 阅读

相关奇怪的比赛

package Java2012大赛; / / 某电视台举办了低碳生活大奖赛。题目的计分规则相当奇怪：每位选手需要回

布满荆棘的人生/ 2022年03月20日 18:46/ 0 赞/ 222 阅读

相关 floyd算法

floyd算法是通过动态规划特别是记住公式，f[i, j, k]表示从i走到j的路径上除i和j点外只经过1到k的点的所有路径的最短距离。那么f[i, j, k] = m

喜欢ヅ旅行/ 2021年06月22日 15:37/ 0 赞/ 423 阅读