#include <iostream>
#include <fstream>
#include <cstdlib>
#include <vector>
#include <queue>
#include <time.h>
#include <unistd.h>
#define IN_FILE "tribut.in"
#define OUT_FILE "tribut.out"
#define MAX_CAP 10000
#define FLOW_USE_EK 1
#define GEN_TESTS 0
#define MIN(a,b) (((a) < (b)) ? (a) : (b))
using namespace std;
class Graph {
int num_nodes, num_planets, num_unions, source, sink;
long flow_value;
vector< vector < pair<int, int> > > edges;
vector< vector<int> > c;
vector< vector<int> > f;
vector<int> excess;
vector<int> height;
void max_flow_push_relabel();
void max_flow_EK();
int push();
int relabel();
vector<int> bfs_rg();
public:
Graph(vector<int>, vector<int>, vector< vector<int> >);
void max_flow();
long get_max_flow();
void print_flow();
void print_capacity();
};
void Graph::print_flow()
{
for (int u = 0; u < num_nodes; u++)
{
for (int v = 0; v < num_nodes; v++)
{
cout << f[u][v] << " ";
}
cout << "\n";
}
cout << "-----------------" << "\n";
}
void Graph::print_capacity()
{
for (int u = 0; u < num_nodes; u++)
{
for (int v = 0; v < num_nodes; v++)
{
cout << c[u][v] << " ";
}
cout << "\n";
}
cout << "-----------------" << "\n";
}
long Graph::get_max_flow()
{
flow_value = 0;
for (vector< pair<int, int> >::iterator it = edges[source].begin(); it != edges[source].end(); ++it)
{
flow_value += f[source][it->first];
}
return flow_value;
}
Graph::Graph(vector<int> planets, vector<int> unions, vector< vector<int> > union_planets)
{
num_nodes = planets.size() + unions.size() + 2;
num_planets = planets.size();
num_unions = unions.size();
source = 0;
sink = planets.size() + unions.size() + 1;
flow_value = 0;
c.assign(num_nodes, vector<int>(num_nodes, 0));
f.assign(num_nodes, vector<int>(num_nodes, 0));
edges.assign(num_nodes, vector < pair<int, int> >());
// vertex 0 is the source
// vertices 1 .. num_planets are the planets
// vertices num_planets + 1 .. num_planets + num_unions are the unions
// vertex num_unions + 1 is the sink
for (int i = 0; i < planets.size(); i++)
{
c[source][i + 1] = planets[i];
edges[source].push_back(pair<int, int>(i + 1, planets[i]));
}
for (int i = 0; i < unions.size(); i++)
{
c[num_planets + i + 1][sink] = unions[i];
edges[num_planets + i + 1].push_back(pair<int, int>(sink, unions[i]));
}
for (int i = 0; i < union_planets.size(); i++)
{
for (int j = 0; j < union_planets[i].size(); j++)
{
c[union_planets[i][j]][num_planets + i + 1] = MAX_CAP;
edges[union_planets[i][j]].push_back(pair<int, int>(num_planets + i + 1, MAX_CAP));
}
}
}
int Graph::push()
{
// find an edge (u, v) with excess[u] > 0, cf(u, v) > 0 and height[u] = height[v] + 1
int push_ok = 0;
for (int u = 0; u < num_nodes && !push_ok; u++)
{
if (excess[u] > 0)
{
for (int v = 0; v < num_nodes; v++)
{
int cf = c[u][v] - f[u][v];
if (height[u] == height[v] + 1 && cf > 0)
{
// edge is ok to push flow
int flow_uv = MIN(cf, excess[u]);
f[u][v] += flow_uv;
f[v][u] -= flow_uv;
excess[u] -= flow_uv;
excess[v] += flow_uv;
push_ok = 1;
break;
}
}
}
}
return push_ok;
}
int Graph::relabel()
{
int relabel_ok = 0;
// find vertex u with excess[u] > 0 and for all edges (u, v) with cf(u, v) > 0 , l[u] <= l[v]
// the sink is never relabeled!
for (int u = 0; u < num_nodes && !relabel_ok; u++)
{
if (excess[u] > 0 && u != sink)
{
int min_dv = 2 * num_nodes; // max value for height function
for (int v = 0; v < num_nodes && height[u] <= min_dv; v++)
{
int cf = c[u][v] - f[u][v];
if (cf > 0)
{
min_dv = MIN(min_dv, height[v]);
}
}
if (min_dv != 2 * num_nodes && height[u] <= min_dv)
{
height[u] = min_dv + 1;
// cout << u << height[u];
relabel_ok = 1;
}
}
}
return relabel_ok;
}
void Graph::max_flow_push_relabel()
{
excess.assign(num_nodes, 0);
height.assign(num_nodes, 0);
height[source] = num_nodes;
for (vector< pair<int, int> >::iterator it = edges[source].begin(); it != edges[source].end(); ++it)
{
excess[it->first] = it->second;
f[source][it->first] = it->second;
f[it->first][source] = - it->second;
}
while (1)
{
// try push
int push_ok = push();
int relabel_ok = false;
// try relabel
if (!push_ok)
{
relabel_ok = relabel();
}
if (!push_ok && !relabel_ok)
{
break;
}
}
}
vector<int> Graph::bfs_rg()
{
vector<int> min_path;
vector<int> visited (num_nodes, 0);
vector<int> parent (num_nodes, -1);
queue<int> q;
visited[source] = 1;
q.push(source);
while (!q.empty())
{
int u = q.front();
q.pop();
if (u == sink)
{
break;
}
for (int v = 0; v < num_nodes; v++)
{
int cf = c[u][v] - f[u][v];
if (visited[v] == 0 && cf > 0)
{
visited[v] = 1;
parent[v] = u;
q.push(v);
}
}
}
int u = sink;
while (parent[u] != -1)
{
min_path.insert(min_path.begin(), u);
u = parent[u];
}
// for (int i = 0; i < min_path.size(); i++)
// {
// cout << min_path[i] << " ";
// }
// cout << "\n";
return min_path;
}
void Graph::max_flow_EK()
{
while (1)
{
vector<int> min_path = bfs_rg();
if (min_path.size() == 0)
{
break;
}
else
{
int min_cf = MAX_CAP;
int prev_u = source;
for (int i = 0; i < min_path.size(); i++)
{
int curr_u = min_path[i];
min_cf = MIN(min_cf, c[prev_u][curr_u] - f[prev_u][curr_u]);
prev_u = curr_u;
}
prev_u = source;
for (int i = 0; i < min_path.size(); i++)
{
int curr_u = min_path[i];
f[prev_u][curr_u] += min_cf;
f[curr_u][prev_u] -= min_cf;
prev_u = curr_u;
}
// print_flow();
// sleep(1);
}
}
}
void Graph::max_flow()
{
if (FLOW_USE_EK)
{
max_flow_EK();
}
else
{
max_flow_push_relabel();
}
}
void gen_tests()
{
/*
Pe prima linie se află numărul de teste, T.
* După aceea, pentru fiecare test sunt citite următoarele informații:
Prima linie a unui test conține două numere întregi separate prin spațiu:
* N - numărul de sisteme solare și M - numărul de uniuni comerciale.
Următoarea linie conține N numere întregi separate prin spațiu,
* reprezentând tributul maximal ce poate fi plătit de fiecare sistem solar pe baza veniturilor sale (tribut[i], 1 <= i <= N).
Dupa aceea, urmează M linii pentru fiecare uniune comercială. Fiecare linie începe cu două numere întregi:
* primul conține numărul de sisteme solare care fac parte din uniune - P,
* iar al doilea tributul maximal plătit de către toate țările din uniune conform tratatului semnat cu Imperiul Galactic (tribut[j], 1 <= j <= M).
* Urmează apoi cele P sisteme solare din uniunea curentă indexate între 1..N.
*/
ofstream out;
out.open(IN_FILE);
srand(time(NULL));
out << 10 << "\n";
for (int i = 1; i <= 9; i++)
{
int n = i * 10;
int m = i * 8;
out << n << " " << m << "\n";
for (int j = 0; j < n; j++)
{
int tribute = rand() % 5000;
if ( tribute > 1000 && tribute < 2000)
{
tribute = 0;
}
if (j > 0)
{
out << " ";
}
out << tribute;
}
out << "\n";
for (int j = 0; j < m; j++)
{
int tribute = rand() % 9000;
if ( tribute > 1000 && tribute < 5000)
{
tribute = 0;
}
vector<int> union_planets;
// generate longer unions
int planet = 1 + rand() % 10;
int step = 4 + rand() % 4;
if ( j % 10 == 0)
{
// generate larger unions
step = 2 + rand() % 3;
}
while (planet <= n){
union_planets.push_back(planet);
planet += step;
}
out << union_planets.size() << " " << tribute;
for (int k = 0; k < union_planets.size(); k++)
{
out << " " << union_planets[k];
}
out << "\n";
}
}
out.close();
}
int main(int argc, char **argv)
{
if (GEN_TESTS)
{
gen_tests();
}
freopen(IN_FILE, "r", stdin);
freopen(OUT_FILE, "w", stdout);
int num_tests;
cin >> num_tests;
for (int i = 0; i < num_tests; i++)
{
int n, m;
cin >> n >> m;
vector<int> planet_tributes(n, 0);
vector<int> union_tributes(m, 0);
vector< vector<int> > union_planets;
for (int j = 0; j < n; j++)
{
cin >> planet_tributes[j];
}
for (int j = 0; j < m; j++)
{
int num_union_planets;
vector<int> curr_union_planets;
cin >> num_union_planets >> union_tributes[j];
for (int k = 0; k < num_union_planets; k++)
{
int union_planet;
cin >> union_planet;
curr_union_planets.push_back(union_planet);
}
union_planets.push_back(curr_union_planets);
}
Graph* g = new Graph(planet_tributes, union_tributes, union_planets);
g->max_flow();
// g->print_flow();
// g->print_capacity();
cout << g->get_max_flow() << "\n";
delete g;
}
return 0;
}