Cow Contest——Floyed+連通性判斷

【題目描述】
N (1 ≤ N ≤ 100) cows, conveniently numbered 1…N, are participating in a programming contest. As we all know, some cows code better than others. Each cow has a certain constant skill rating that is unique among the competitors.

The contest is conducted in several head-to-head rounds, each between two cows. If cow A has a greater skill level than cow B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B), then cow A will always beat cow B.

Farmer John is trying to rank the cows by skill level. Given a list the results of M (1 ≤ M ≤ 4,500) two-cow rounds, determine the number of cows whose ranks can be precisely determined from the results. It is guaranteed that the results of the rounds will not be contradictory.
Input

  • Line 1: Two space-separated integers: N and M

  • Lines 2…M+1: Each line contains two space-separated integers that describe the competitors and results (the first integer, A, is the winner) of a single round of competition: A and B
    Output

  • Line 1: A single integer representing the number of cows whose ranks can be determined
     
    Sample Input

5 5
4 3
4 2
3 2
1 2
2 5

Sample Output

2

【題目分析】
需要將題目轉化成圖的問題,假如我們我打贏看作一條有向邊,那么對于每個節點,我們判斷其他節點能否到達他(比他厲害)或者他能否到達其他節點(比他菜),如果所有節點都可以,那么他的排名就是唯一確定的,所以我們用一個Floyed判斷一下

【AC代碼】

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<climits>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;typedef long long ll;
const int MAXN=105;
bool a[MAXN][MAXN],flag;
int n,m,ans;void Floyed()
{for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){a[i][j]=a[i][j] || (a[i][k] && a[k][j]);}}}
}int main()
{int u,v;while(~scanf("%d%d",&n,&m)){memset(a,0,sizeof(a));ans=0;for(int i=0;i<m;++i){scanf("%d%d",&u,&v);a[u][v]=true;}Floyed();for(int i=1;i<=n;i++){flag=true;for(int j=1;j<=n;j++){if(i==j) continue;if(!a[i][j] && !a[j][i]){flag=false;break;}}if(flag) ans++;}printf("%d\n",ans);}return 0;
}

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/384080.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/384080.shtml
英文地址,請注明出處:http://en.pswp.cn/news/384080.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

C++11 標準新特性:委派構造函數

https://www.ibm.com/developerworks/cn/rational/1508_chenjing_c11/index.html陳 晶2015 年 8 月 11 日發布WeiboGoogle用電子郵件發送本頁面 1本文首先介紹了在委派構造函數提出之前類成員構造所面臨的問題&#xff0c;再結合實例介紹了委派構造函數的用法&#xff0c;并說明…

順序表實現隊列

一. 隊列相關概念 隊列是只允許在一段進行插入元素, 在另一端進行刪除元素的線性表,即只允許對隊列進行尾插,頭刪的操作.隊列具有先進先出, 后進后出的特性. ???????? 1.初始化 void SeqQueInit(SeqQue* q) {if(q NULL){return;//非法輸入}q -> head 0;q -> …

Arbitrage——判斷正環Bellman-Ford/SPFA

【題目描述】 Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 US Dollar buys 0.5 British pound, 1 British pound buys 10.0 French …

鏈表實現隊列

上篇博客是用順序表實現隊列, 現在用雙向帶頭結點帶環鏈表實現對隊列的出隊列, 入隊列, 取隊首元素, 以及銷毀隊列的相關操作 1.初始化鏈表 void DLinkQueInit(DLinkQue** q) {if(q NULL){return;//非法輸入}if(*q NULL){return;//非法輸入帶頭結點的鏈表至少有一個傀儡結點…

HDU - 1796——容斥原理+二進制枚舉

【題目描述】 Now you get a number N, and a M-integers set, you should find out how many integers which are small than N, that they can divided exactly by any integers in the set. For example, N12, and M-integer set is {2,3}, so there is another set {2,3,4,…

數據結構學習(二)——單鏈表的操作之頭插法和尾插法創建鏈表

http://blog.csdn.net/abclixu123/article/details/8210109 鏈表也是線性表的一種&#xff0c;與順序表不同的是&#xff0c;它在內存中不是連續存放的。在C語言中&#xff0c;鏈表是通過指針相關實現的。而單鏈表是鏈表的其中一種&#xff0c;關于單鏈表就是其節點中有數據域和…

信號的基本概念以及信號的產生

一. 信號產生的場景 1. 用戶輸入命令, 在shell 啟動一個前臺進程 ???? 2. 當用戶按一下 Ctrl C 的時候,從鍵盤產生一個硬件中斷 ???? 3. 此時CPU 正在執行這個進程的帶代碼, 則該進程的執行代碼暫停執行, CPU 從用戶態切換到內核態處理該硬件中斷. ???? 4. 中斷…

HDU - 1028——母函數入門

【題目描述】 “Well, it seems the first problem is too easy. I will let you know how foolish you are later.” feng5166 says. “The second problem is, given an positive integer N, we define an equation like this: Na[1]a[2]a[3]…a[m]; a[i]>0,1<m<N;…

信號的阻塞

一. 阻塞信號 1.信號的相關概念 ????(1) 遞達: 實際執行信號的處理動作稱為信號的遞達 ????(2) 未決: 信號從產生到遞達之間的過程叫做信號的未決 ????(3) 阻塞: 進程可以選擇阻塞某個信號, 被阻塞的信號產生時將保持在未決狀態, 直到進程解除該信號的屏蔽, 才…

POJ 1511 Invitation Cards——Dijkstra優先隊列優化+反向建圖

【題目描述】 In the age of television, not many people attend theater performances. Antique Comedians of Malidinesia are aware of this fact. They want to propagate theater and, most of all, Antique Comedies. They have printed invitation cards with all the…

鏈棧 尹成

http://blog.csdn.net/itcastcpp/article/details/39271661 今天&#xff0c;我們一起用C寫鏈棧&#xff0c;具體如下。 LinkStack.h具體內容&#xff1a; [cpp] view plaincopy #include "StackNode.h" template<typename Type> class LinkStack{ publ…

信號的捕捉以及SIGCHLD信號

一. 信號的捕捉定義 用戶提供一個處理函數, 要求內核在處理信號時必須切換到用戶態,執行這個函數, 這種方式就叫做信號的捕捉 二. 圖解信號的捕捉過程 1. 由上圖可以看出,當處理信號的執行動作時用戶自定義的時候,此時就需返回該函數去調用該函數, 這就叫做信號的捕捉. 以前我…

鏈隊 尹成

http://blog.csdn.net/itcastcpp/article/details/39271691 今天&#xff0c;我們一起用C寫一個鏈對&#xff0c;具體如下所示。 LinkQueue.h具體內容如下&#xff1a; [cpp] view plaincopy #include "QueueNode.h" template<typename Type> class LinkQueu…

強連通分量入門——Trajan算法

今天學習了強連通分量。 【參考博客】 如果覺得我講的有些地方難以理解或者存在問題&#xff08;歡迎留言&#xff09;&#xff0c;可以看一下我借鑒的一些大佬的博客&#xff1a; 傳送門1 傳送門2 【知識儲備】 首先我們需要對幾個定義有一些概念&#xff1a; 強連通&#xff…

最小棧的實現

所謂最小棧, 就是當前棧頂元素最小, 我們可以這樣做, 每次在入棧之前, 將待入棧元素與棧頂元素相比, 每次現將待入棧的元素先入棧, 再將帶入棧的元素和較小的元素入棧, 這樣就可以保證每次棧頂元素是最小元素. 在出棧的時候規定每次出棧兩個元素,這樣就可以保證在出棧之后棧頂元…

用C++實現單鏈表的創建、逆置和輸出 的兩種方法

http://blog.csdn.net/lfeng_coding/article/details/47300563 題目描述&#xff1a;在已知單鏈表頭節點的情況下&#xff0c;設計算法逆置單鏈表并輸出 方法一&#xff1a;采用首先將頭節點指向空&#xff0c;讓其變為尾節點&#xff0c;然后利用中間節點 p、q 將其后的節點一…

兩個棧實現一個隊列

利用兩個棧實現一個隊列思路是這樣的. 首先這個隊列包含兩個棧, 然后一個棧用來入隊列, 一個棧用來出隊列 typedef struct QueBy2Stack {SeqStack input;SeqStack output; }QueBy2Stack; 1. 初始化 void QueBy2StackInit(QueBy2Stack* stack) {if(stack NULL){return;//非法…

HDU 5934:Boom——強連通分量+縮點

【題目描述】 There are N bombs needing exploding.Each bomb has three attributes: exploding radius ri, position (xi,yi) and lighting-cost ci which means you need to pay ci cost making it explode.If a un-lighting bomb is in or on the border the exploding ar…

Linux--線程死鎖

http://blog.csdn.net/gebushuaidanhenhuai/article/details/73799824 線程為什會死鎖&#xff1f;&#xff1f;“鎖”又是什么東西&#xff1f;我們這篇博客主要講一下為什么要給線程加鎖&#xff0c;為什么會出現線程死鎖&#xff0c;線程死鎖怎么解決。 互斥鎖 在我的上篇博…

兩個隊列實現一個棧

用兩個隊列實現一個棧的原理是這樣的. 規定兩個隊列, 必須有一個隊列是非空, 一個隊列是空.每次入棧時必須往非空隊列中入, 而每次出棧時, 必須將非空隊列里的元素裝到空隊列中, 直到非空隊列中只有一個元素時, 此時就將剩下的這個元素出棧即可. 而取棧頂元素時, 和出棧一樣, 先…