$24
问题 A: Adjacency Matrix Solution
题目描述
Give you a directed graph G with n nodes and m edges. Please print the adjacency matrix A of G. Hints: adjacency matrix is a way to represent a graph. Suppose we have a directed graph G, if there is an edge from node i to node j in G, we have A[i][j] = 1 in G’s corresponding adjacency matrix A, otherwise, A[i][j] = 0.
输入
The first line will be an integer T (1 <= T <= 50). T is the number of test case.
For each test case, the first line will be two integers n and m. ( 1 <= n <= 500, 0 <= m <= n*n)
Then there will be m lines. Each line will have two integers x y. x y means there is an edge from x to y. All nodes are labeled from 1 to n.
输出
For each test case, print the adjacency matrix.
样例输入
2
5
1 2
2 1
1 3
2
2 3
1 0
样例输出
0 1 1
1 0 1
0 1 0
0
问题 B: Reachability Testing
题目描述
In a graph G, if we can find a path from node x to node y. We say x can reach y. Now give you a directed graph G with n nodes and m edges. There are Q queries. Each query will contain two integers x y. If x can reach y, print YES. Otherwise, print NO.
Note: We guarantee there is at most one edge from node i to node j.
输入
The first line will be an integer T (1 <= T <= 50). T is the number of test case.
For each test case, the first line will be two integers n and m. (1 <= n <= 1000, 0 <= m <= min(n * n, 100000))
Then there will be m lines. Each line will have two integers x y. x y means there is an edge from x to y.
After that, there is an integer Q. (1 <= Q <= 500) Then, there will be Q lines. Each line will have two integers x y.
All nodes are labeled from 1 to n.
输出
For each query, if x can reach y, print YES. Otherwise, print NO.
样例输入
1
7 7
6
6 4
4 3
3 5
5 1
2 7
7 2
6
2
2 7
7 2
3 6
4 6
5 4
样例输出
NO
YES
YES
YES
YES
YES
提示
For the first sample, 1 cannot reach 2. Since 2 and 7 form a ring.
For the second sample, 2 can reach 7 directly
For the third sample, 3 - 5 - 1 - 6 is one path.
问题 C: Shortest path
题目描述
Alice has a graph of n nodes and m undirected edges. These nodes are numbered from 1 to n, she wants to know the shortest path from s to other nodes. If there is no path between s and node i, output -1.
输入
The first line will be an integer T, which is the number of the test cases(1 <= T <= 10). For each test case, the first line will be three integers, n(1 <= n <= 105), m(1 <= m <= 5*105) and s(1 <= s <= n). Then followed by m lines, each line will be two integers x and y, it means that there is an undirected edge between x and y.
输出
For each test output numbers in one line. For the i-th number means the shortest path between s and node i, if the path does noe exist, then print -1 instead.
样例输入
1
4 4 1
2
2 3
3 4
4
样例输出
0 1 2 1
问题 D: Clique
题目描述
Bob has a graph of n nodes and m undirected edges. These nodes are numbered from 1 to n, he does not know how many cliques this graph has of size 4. Then, he turns to you for help.
The definition of clique of nodes:
there is at least one edge between every two node x, y(x != y).
输入
The first line will be an integer T, which is the number of the test cases(1 <= T <= 10). For each test case, the first line will be two integers n and m(1 <= n <= 75, 1 <= m <= 105). Then followed by m lines, each line will be two integers x and y, it means that there is an undirected edge between x and y.
输出
For each test output the number of cliques in one line.
样例输入
1
6
1 2
1 3
1 4
2 3
2 4
3 4
样例输出
1
问题 E: Connected group
题目描述
Carol has a matrix of n rows and m columns. Every grid(the coordinate are from 1) in the matrix has a number representing its color. If you stand on one grid, you can move to an adjacent grid if you satisfy these two requirements:
If you stand on (x, y), then (x + 1, y), (x - 1, y), (x, y - 1), (x, y + 1) are adjacent to you.
The color in your position are the same as the grid you are going to.
If you can reach one grid from another grid, then they are in the same group.
Now, you need to calculate how many groups the matrix has.
The most important thing is the first column are adjacent to the last column.
输入
The first line will be an integer T, which is the number of the test cases(1 <= T <= 10). For each test case, the first line will be two integers n and m(1 <= n <= 1000, 1 <= m <= 1000). Then followed by n lines, each line will be m integers. The j-th integer in the i-th line means the color of the grid(i, j)(1 <= color <= 5).
输出
For each test output The number of groups.
样例输入
1
3 4
1 2 3 5
1 2 3 1
1 3 3 5
样例输出
5
问题 F: Longest path
题目描述
David has a graph of n nodes and m directed edges, and he wants to know the longest path in this graph.
We promise that there is no loop in the graph.
输入
The first line will be an integer T, which is the number of the test cases(1 <= T <= 10). For each test case, the first line will be two integers n and m(1 <= n <= 100000, 1 <= m <= 200000). Then followed by m lines, each line will be three integers x, yand z(1 <= z <= 300000), it means that there is an directed edge weighted z from x to y.
输出
For each test output the longest path in this graph.
样例输入
1
4
1 2 5
2 3 4
1 3 10
1 3 20
样例输出
问题 G: Ancestor
题目描述
Ella has a tree of n nodes. There are m queries, each query has two integers x and y to ask whether y is an ancestor of x or not, and x is an ancestor of x. However, Ella does not know how to deal with it. Now, you need to show how clever you are to solve such a easy problem.
输入
The first line will be an integer T, which is the number of the test cases(1 <= T <= 10). For each test case, the first line will be two integers n(1 <= n <= 1.5105) and m(1 <= m <= 1.5105). Then followed by n - 1 lines, each line will be two integers x and y, it means that y if the father of x. Then followed by m lines, each line will be two integers x and y, it means a query(x, y). If y is an ancestor of x, output Yes, else output No.
输出
For each test output m lines to answer the queries.
样例输入
1
1
1
1 2
样例输出
No
问题 H: Nearest pair
题目描述
Fred has a graph of n nodes and m undirected edges(the length of each edge is 1). These nodes are numbered from 1 to n. Now, he gives you a node set whose size is K. He askes you to calculate the shortest path between a node pair belonging to the node set.
输入
The first line will be an integer T, which is the number of the test cases(1 <= T <= 10). For each test case, the first line will be three integers and n, m and K(1 <= n <= 300000, 1 <= m <= 400400, 1 <= K <= n). Then followed by m lines, each line will be two integers x and y, it means that there is an un directed edge be x and y. The next line will be K unique integers , each integer represents a node in the node set.
输出
For each test output the distance of the shortest path, if the path does noe exist, then print-1 instead.
样例输入
1
5 4 2
2
2 3
3 4
4 5
5
样例输出
4
问题 I: Sum of value
题目描述
Grace has a connected graph of n nodes and m undirected edges. These nodes are numbered from 1 to n. Each edge has a value. The graph does not contain self-loop and there is at most one edge between any two nodes. Addtionally, there are at most two non-intersect paths, which shares no common edges, between any two nodes. She defines W(x,y) as the minimum cost to let no path between x and y. The cost to cut one edge is the value of the edge, and once you cut an edge, the edge disappears in the graph. Every time you need to calculate the minimum cost of a pair, you need to cut the edges from the original graph. every W is independent. At last, Grace asks you to calculate this
sum of W(i,j)(i != j)
输入
The first line will be an integer T, which is the number of the test cases(1 <= T <= 10). For each test case, the first line will be three integers n, m(1 <= n <= 105, 1 <= m <= 1.5*(n - 1)). Then followed by m lines, each line will be three integers x, y and z(1 <= z <= 109), it means that there is an undirected edge between x and y whose value is z.
输出
For each test output the answer for the query in one line.
样例输入
1
2
1 2 1
2 3 1
样例输出
3
