Beyond the Void
BYVoid
USACO JAN08 Silver Cow Contest 奶牛的比赛

由题意可知,当一头牛能胜过的牛与能输给的牛的和为全部的牛时,该牛的名次可知。

根据关系构图,首先每头牛为一个顶点。如果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

相关日志