2019_GDUT_新生专题 图论 --- A

A — Cow Contest

原题链接:https://vjudge.net/contest/351234#problem/A

题目大意:

很多cow进行两两pk,给出cow的数目和一些pk的结果,问能确定排名的cow的数目。

题目分析:

这是一道图论,出度和入度的问题。
如果 某cow 打败过 a个(出度数),而被b个打败过(入度数),且满足a+b就是除了本身的所以其他cow的数目,那么就可以确定他的排名就是b+1,即满足出度+入度=顶点个数-1。

代码实现:

#include<iostream>
#include<cstdio>
#define INF 1000001
//Floyd算法
using namespace std;

int n, m, ans;
//牛与牛之间的关系
int dist[102][102];

int main()
{
    int i, j ,k;
    int a, b;

    ans = 0;
    cin >> n >> m;
    //初始化
    for(i=1; i<=n; i++){
        for(j=1; j<=n; j++){
            if(i == j) dist[i][j] = 0;
            else dist[i][j] = INF;
        }
    }
    for(i=1; i<=m; i++){
        cin >> a >> b;
        dist[a][b] = 1; //a->b  代表a打败b
    }
    //Floyd算法
    for(k=1; k<=n; k++)
        for(i=1; i<=n; i++)
            for(j=1; j<=n; j++) //i能否通过k来确定i比j强
                if(dist[i][j] > dist[i][k] + dist[k][j])
                    dist[i][j] = dist[i][k] + dist[k][j];

    int check;
    for(i=1; i<=n; i++){
        check = 0;
        for(j=1; j<=n; j++){
            if(dist[i][j] != 0 && dist[i][j] != INF) check++; //i比j强?
            if(dist[j][i] != 0 && dist[j][i] != INF) check++; //i不比j强?
        }
        if(check == n - 1) ans++; //比i弱的数目,加上比i强的数目,等于n-1则能确定i的排名
    }
    cout << ans << endl;


    return 0;
}


最后,希望路过的dl们能给予改进的建议!

2019_GDUT_新生专题 图论 --- A2019_GDUT_新生专题 图论 --- A csdn_xieql 发布了10 篇原创文章 · 获赞 0 · 访问量 111 私信 关注
上一篇:线段树


下一篇:loj 6029 「雅礼集训 2017 Day1」市场