Codechef GALACTIK решение - PullRequest
       47

Codechef GALACTIK решение

0 голосов
/ 13 мая 2018

Вот ссылка на проблему:

Я использовал алгоритм поиска объединения для решения проблемы. Код:

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define INT 100000000
unordered_map<ll, ll> parent;
unordered_map<ll, ll> depth;
std::vector<ll> cost;
ll find_set(ll x) {
    if (x == parent[x])return x;
    parent[x] = find_set(parent[x]);
    return parent[x];
}
void union_set(ll x, ll y) {
    /*
    Creating a disjoint set such that the node with smallest cost 
    being the root using union-rank concept. 
    */
    ll rep1 = find_set(x), rep2 = find_set(y);
    if (depth[rep1] > depth[rep2])parent[rep1] = rep2;
    else if (depth[rep2] >= depth[rep1])parent[rep2] = rep1;
}
int main() {
    ll n, m;
    cin >> n >> m;
    ll c[m + 1][3];
    for (ll i = 1; i <= m; i++) {
        cin >> c[i][1] >> c[i][2]; //Accepting the edges
    }
    for (ll i = 1; i <= n; i++) {
        parent[i] = i;
        cin >> depth[i];
        if (depth[i] < 0)depth[i] = INT;
        /*we assume that each negative cost is replaced by a very 
          large positive cost.*/ 
    }
    for (ll i = 1; i <= m; i++) {
        union_set(c[i][1], c[i][2]);
    }
    set<ll> s;
    std::vector<ll> v;
    //storing representatives of each connected component
    for (auto i = 1; i <= n; i++)s.insert(depth[find_set(i)]);
    for (auto it = s.begin(); it != s.end(); it++)v.push_back(*it);
    sort(v.begin(), v.end());
    if (s.size() == 1) {
        //Graph is connected if there is only 1 connected comp
        cout << 0 << endl;
        return 0;
    }
    bool flag = false;
    ll p = 0;
    for (ll i = 1; i < v.size(); i++) {
        if (v[i] == INT) {
            flag = true;
            break;
        }
        p += (v[0]+v[i]);
    }
    if (flag)cout << -1 << endl;
    else cout << p << endl;
    return 0;
}

Логика, используемая в моей программе: Чтобы найти ответ, возьмите минимальное значение из всех допустимых значений в связанном компоненте. Теперь, чтобы связать график, возьмите минимальное значение из всех значений, которые мы получили на предыдущем шаге, и сделайте ребро от этого узла до всех остальных узлы. Если граф уже подключен, ответ равен 0. Если существует связанный компонент, в котором все узлы недопустимы для выбора, то ответ невозможен (-1).

Но это решение не принято? Что с ним не так?

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...