浙江财经大学
信工学院ACM集训队

CSU 1802 小X的战斗力

本文由 Ocrosoft 于 2016-08-31 22:09:38 发表

Description

小X才不是战五渣!为了证明这一点,小X进行了一些调查。

小X收集了班上一些同学之间决斗的胜负情况。决斗是两个人之间实力的比拼,实力用战斗力来衡量。小X猜想,战斗力高的人一定会在决斗中取得胜利。决斗一定会分出胜负,因此不存在战斗力相同的两人。

小X在调查分析自己的实力排名的同时,也顺便知道了其他一些同学的战斗力排名情况。现在你获取了这一批数据,请求出小X的调查结果。

因为小X并不怎么记得班上同学的名字,于是在数据中用数字来给同学们编号,从1到N。

小X把自己标为1号。

Input

第一行为数据组数TT<=10

对于每组数据:

第一行为两个整数NM1<=N<=1501<=M<=5000)。N表示小X班上同学的总人数,M表示小X收集了M次决斗的信息。

接下来M行,每行两个整数AB1<=A,B<=N,AB),描述了一次决斗,决斗的结果是同学A胜出。

Output

对于每组数据:

如果小X的猜想没错,输出两行。第一行,如果可以确定小X的排名则输出一个整数P表示小X的排名,否则输出-1;第二行,输出一个整数K表示可以确定具体名次的班上同学的数量(包括小X自己)。

如果小X的猜想有误,输出一行一个字符串“Wrong”,没有引号。

Sample Input

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

Sample Output

-1
2
Wrong

Hint

对于第一组数据,可以确定名次的同学有2个,2号第45号第5

Solution

思路:不能拓扑排序的时候是Wrong,能拓扑排序的时候,进行一遍Floyd(的变形),不求最短路,只求i能不能(通过k)到达j。之后对每个点进行讨论,如果edge[i][j]==1,说明i能走到j,sum1++用来记录i能到达的点的数量;如果edge[j][i]==1,说明j能走到i,sum2++用来记录能到达i的点的数量。如果sum1+sum2==n-1,那么点i的位置是可以确定的,因为之前拓扑已经确定没有成环,那么edge[i][j]和edge[j][i]都等于1的时候说明无法确定顺序,两者相加等于n-1的时候,就都能确定顺序。

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define ms(a) memset(a,0,sizeof(a))
typedef long long LL;
const LL LINF = 1e17;
const int INF = INT_MAX / 2;
const int MAXN = 150 + 10;
const int MOD = 100000;
int gcd(int a, int b)
{
	if (!b)return a;
	return gcd(b, a%b);
}
using namespace std;
queue<int> q;
bool edge[MAXN][MAXN];
bool reach[MAXN][MAXN];
int in[MAXN];
int n, m;
bool topo()
{
	for (int i = 1; i <= n; i++)
		if (!in[i])q.push(i);
	int cnt = 0;
	while (!q.empty())
	{
		int t = q.front(); q.pop();
		cnt++;
		for (int i = 1; i <= n; i++)
		{
			if (edge[t][i])
			{
				in[i]--;
				if (!in[i])q.push(i);
			}
		}
	}
	return cnt == n;
}
void floyd()
{
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				edge[i][j] |= edge[i][k] && edge[k][j];
}
int main()
{
	int N;
	cin >> N;
	while (N--)
	{
		cin >> n >> m;
		ms(edge); ms(in); ms(reach);
		for (int i = 0; i < m; i++)
		{
			int u, v;
			scanf("%d%d", &u, &v);
			if (!edge[u][v])
			{
				edge[u][v] = 1;
				in[v]++;
			}
		}
		if (!topo())printf("Wrong\n");
		else
		{
			floyd();
			int loc = -1, ans = 0;
			for (int i = 1; i <= n; i++)
			{
				int sum1 = 0, sum2 = 0;
				for (int j = 1; j <= n; j++)
				{
					if (edge[i][j])sum1++;
					if (edge[j][i])sum2++;
				}
				if (sum1 + sum2 + 1 == n)
				{
					ans++;
					if (i == 1)loc = sum2 + 1;
				}
			}
			printf("%d\n", loc);
			printf("%d\n", ans);
		}
	}
	return 0;
}

欢迎转载,请保留出处与链接。Ocrosoft » CSU 1802 小X的战斗力

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址