Cod sursa(job #868598)

Utilizator VisuianMihaiMihai Visuian VisuianMihai Data 31 ianuarie 2013 12:02:06
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <vector>
#include <set>
using namespace std;
ifstream fin("dominouri.in");
ofstream fout("dominouri.out");
vector<int>g[100001];
multiset<int>ss[100001];
int k[100001], sol[100001],n, x, nr;
void Dfs(int x)
{
    !g[x].size()?sol[x]=1:sol[x]=0;
    for ( vector<int>::iterator it = g[x].begin(); it < g[x].end(); it++ )
    {
            Dfs(*it);
            ss[x].insert(sol[*it]);
    }
    multiset<int>::iterator it2=ss[x].begin();
    while ( k[x]-- )
        sol[x] += *(it2++);
}
int main()
{
    fin >> n;
    for ( int i = 1; i <= n; i++ )
    {
        fin >> nr;
        while ( nr-- )
        {
            fin >> x;
            g[i].push_back(x);
        }
    }
    for ( int i= 1; i <= n; i++ )
        fin >> k[i];
    Dfs(1);
    fout << sol[1];
    fin.close();
    fout.close();
    return 0;
}