Football Games

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 466 Accepted Submission(s): 171

Problem Description
A mysterious country will hold a football world championships—Abnormal Cup, attracting football teams and fans from all around the world. This country is so mysterious that none of the information of the games will be open to the public till the end of all the matches. And finally only the score of each team will be announced.

At the first phase of the championships, teams are divided into M groups using the single round robin rule where one and only one game will be played between each pair of teams within each group. The winner of a game scores 2 points, the loser scores 0, when the game is tied both score 1 point. The schedule of these games are unknown, only the scores of each team in each group are available.

When those games finished, some insider revealed that there were some false scores in some groups. This has aroused great concern among the pubic, so the the Association of Credit Management (ACM) asks you to judge which groups’ scores must be false.

Multiple test cases, process till end of the input.

//=======================================================
这题……
WA了三次因为没看到输入的第一句话。
这题……怎么说呢
所有球队总分等于m*(m-1)，然后因为最多只有一个0分，一个队的最大得分是m*2-2，奇数分队伍是偶数支。
我最开始还在想是不是要枚举……
MDZZ
//=======================================================

#include <iostream>
using namespace std;

int main()
{
	int T;
	while (cin >> T)
	{
		while (T--)
		{
			int m, s, tots = 0, s1 = 0, s0 = 0;
			bool flag = false;
			cin >> m;
			for (int i = 0; i < m; i++)
			{
				cin >> s;
				if (s % 2 == 1) s1++;
				tots += s;
				if (s == 0) s0++;
				if (s > 2 * m - 2)
				{
					flag = true;
				}
			}
			if ((m*(m - 1) == tots) && (s1 % 2 == 0) && (s0 <= 1) && !flag)
				cout << "T" << endl;
			else cout << "F" << endl;
		}
	}
	return 0;
}

Sparse Graph

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 403 Accepted Submission(s): 133

Problem Description
In graph theory, the complement of a graph G is a graph H on the same vertices such that two distinct vertices of H are adjacent if and only if they are not adjacent in G.

Now you are given an undirected graph G of N nodes and M bidirectional edges of unit length. Consider the complement of G, i.e., H. For a given vertex S on H, you are required to compute the shortest distances from S to all N−1 other vertices.

Input
There are multiple test cases. The first line of input is an integer T(1≤T<35) denoting the number of test cases. For each test case, the first line contains two integers N(2≤N≤200000) and M(0≤M≤20000). The following M lines each contains two distinct integers u,v(1≤u,v≤N) denoting an edge. And S (1≤S≤N) is given on the last line. Output For each of T test cases, print a single line consisting of N−1 space separated integers, denoting shortest distances of the remaining N−1 vertices from S (if a vertex cannot be reached from S, output ``-1" (without quotes) instead) in ascending order of vertex number. Sample Input 1 2 0 1 Sample Output 1 Source 2016 ACM/ICPC Asia Regional Dalian Online //======================================================= 比赛的时候以为是最短路，就开始求补然后突然发现邻接表邻接矩阵好像都没法存补图…… 我居然没从另一个侧面去想一下…… MDZZ…… 比完赛看完题解才知道原来BFS就好了…… //======================================================= 感谢dalao的题解
//=======================================================

#include <iostream>
#include <set>
#include <queue>
#define MAXN 200020
#define MAXM 50005
#define INF  0x3F3F3F3F
using namespace std;

int n, m, edges, g[MAXN], nxt[MAXM], v[MAXM], S, d[MAXN];

void BFS()
{
	set<int> a, b;
	set<int>::iterator it;
	queue<int> Q;
	for (int i = 1; i <= n; i++) d[i] = INF;
	d[S] = 0;
	Q.push(S);
	for (int i = 1; i <= n; i++)
		if (i != S) a.insert(i);
	while (!Q.empty())
	{
		int now;
		now = Q.front(); 
		Q.pop();
		for (int i = g[now]; i; i = nxt[i])
			if (a.find(v[i]) != a.end())
			{
				a.erase(v[i]);
				b.insert(v[i]);
			}
		for (it = a.begin(); it != a.end(); it++)
		{
			Q.push(*it);
			d[*it] = d[now] + 1;
		}
		a.swap(b);
		b.clear();
	}
	for (int i = 1; i < n; i++)
	{
		if (i != S) cout << (d[i] == INF ? -1 : d[i]) << ' ';
	}
	cout << d[n];
	cout << endl;
}

int main()
{
	int T; cin >> T;
	while (T--)
	{
		edges = 0;
		cin >> n >> m;
		for (int i = 1; i <= n; i++) g[i] = 0;
		for (int i = 1; i <= m; i++)
		{
			int U, V;
			cin >> U >> V;
			v[++edges] = V, nxt[edges] = g[U], g[U] = edges;
			v[++edges] = U, nxt[edges] = g[V], g[V] = edges;
		}
		cin >> S;
		BFS();
	}
	return 0;
}