USACO JAN08 Silver Cow Contest 奶牛的比賽
本文正體字版由OpenCC轉換
由題意可知，當一頭牛能勝過的牛與能輸給的牛的和爲全部的牛時，該牛的名次可知。
根據關係構圖，首先每頭牛爲一個頂點。如果i強於j，從i到j建立有向邊，構造出圖G1。根據G1構造G1的逆圖G2。
以圖中的每個頂點i爲起點，遍歷圖G1,G2。記從頂點i開始遍歷G1到的頂點集合爲A，從頂點i開始遍歷G2到的頂點集合爲B。如果A∪B=V (V爲全部頂點集)，則這個牛的名次可知。
/*
ID: cmykrgb1
PROG: contest
LANG: C++
*/
#include <iostream>
#define MAX 101
using namespace std;
class list
{
public:
list *next;
int p;
list(int &tp)
{
p=tp;
next=0;
}
};
class tadjl
{
public:
list *first,*last;
tadjl()
{
first=last=0;
}
void ins(int p)
{
if (first)
last=last->next=new list(p);
else
first=last=new list(p);
}
};
tadjl adjl[MAX],rdjl[MAX];
int N,M,cnt,Ans;
bool vis[MAX];
void init()
{
int i,a,b;
freopen("contest.in","r",stdin);
freopen("contest.out","w",stdout);
cin >> N >> M;
for (i=0;i<M;i++)
{
cin >> a >> b;
adjl[a].ins(b);
rdjl[b].ins(a);
}
}
void dfs(int i,tadjl *L)
{
int j;
list *k;
cnt++;
vis[i]=true;
for (k=L[i].first;k;k=k->next)
{
j=k->p;
if (!vis[j])
{
dfs(j,L);
}
}
}
void solve()
{
int i;
for (i=1;i<=N;i++)
{
memset(vis,0,sizeof(vis));
cnt=0;
dfs(i,adjl);
dfs(i,rdjl);
if (cnt==N+1)
Ans++;
}
}
int main()
{
init();
solve();
cout << Ans << endl;
return 0;
}
上次修改時間 2017-02-03