Решение задачи Изучение языков с Codeforces

С пояснением   Просмотров: 31


В компании «BerCorp» работает n сотрудников. Для официальной переписки утверждено m языков, пронумерованных целыми числами от 1 до m. Для каждого сотрудника известно, какие языки он знает. Возможно даже, что человек не знает ни одного официального языка. Но работники готовы выучить любое количество языков, если только компания оплатит им обучение. Стоимость курса изучения одного языка для одного сотрудника составляет 1 бердоллар.

Определите, какую минимальную сумму денег придется затратить компании, чтобы любой сотрудник мог обратиться к любому другому, возможно, не напрямую (то есть, привлекая других сотрудников для перевода).

Код

#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> mat(2005);
vector<bool> v(1005);
int n,m,c=0,k,t,a=0;
void dfs(int n){
        if(v[n])return;
        v[n]=1;
        for(auto i:mat[n])dfs(i);
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
        cin>>t,c+=t;
        for(int j=0;j<t;j++)
        cin>>k,mat[i+m].push_back(k-1),mat[k-1].push_back(i+m);
}
if(!c)return cout<<n,0;
for(int i=m;i<n+m;i++)if(!v[i])dfs(i),a++;
cout<<a-1;
}

         

Администратор Photo Автор: Администратор


Построим двудольный граф с n вершинами (для сотрудников) в одной доле, и m вершинами (для языков) в другой. Если сотрудник знает язык, значит должно быть ребро между соответствующими вершинами. Теперь задача выглядит понятнее: нужно добавить в граф минимальное количество ребер, чтобы появилась компонента связности, содержащая всех n сотрудников. Очевидно, что это число равно количеству компонент связности, включающих хотя бы одного сотрудника, минус 1. Но есть одно исключение (претест #4): если изначально вообще никто не знает ни один язык, то ответ равен n, так как мы не можем добавлять ребра напрямую между людьми.


Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться