MAXISET - Maximal Independent Set

no tags 

Đọc đề đẹp hơn ở:

You are given an unweighted undirected graph G. Each vertex has a positive weighted associated with it. Weight of a set of vertices is defined as the sum of weights of all vertices in the set.

A set of vertices is called independent if there is no edge in the graph with both endpoints on vertices of this set.

A subgraph induced by a set of vertices is a graph with vertex set as the given set of vertices and edges in the original graph with both endpoints in the given set.

If s denotes a set of vertices, then Query(s, G) = Maximal weighted independent set in the subgraph induced by s.

Given q queries and the description of the graph, you are to output the weight of the Maximal weighted independent set corresponding to each of the queries.


First line contains T, the number of test cases.

Each test case description starts with one line containing 2 integers n and m, denoting the number of vertices and number of edges.

Next line contains n space separated integers denoting the weight of vertices from 0 to n - 1 ( inclusive ).

Next m lines contains two integers u and v ( u != v, 0 ≤ u,v < n ), denoting an undirected edge from u to v.

Next line contains q, the number of querries.

Next q lines contain description of a query. Description of a query starts with an integer denoting the size of set s, followed by the vertices which are members of vertex set s.


For each test case, output q lines containing the answer to each query. Print a blank line BETWEEN the output of multiple test cases.


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




Dataset 1: T ≤ 20, n ≤ 30 , m ≤ 1000, q ≤ 1000 , weight_of_a_vertex ≤ 1000 Time limit: 5s

Dataset 2: T ≤ 10, n ≤ 40, m ≤ 1000, q ≤ 100, weight_of_a_vertex ≤ 1000 Time limit: 5s

Added by:Race with time
Time limit:1.183s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Code Craft 09