Cod sursa(job #1708725)

Utilizator trebedeaTraian Rebedea trebedea Data 27 mai 2016 20:53:22
Problema Tribut Scor Ascuns
Compilator cpp Status done
Runda Marime 10.6 kb
#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;
}