Szczegółowe omówienie zadania Milk Visit z Amerykańskie Olimpiady Informatycznej USACO – grupa srebrna (Silver):
https://youtu.be/KI7un-HU_Hk?t=1421
–
W rozwiązaniu użyto algorytmu Find And Union który jest szczegółowo wyjaśniony w poniższym fragmencie:
https://youtu.be/KI7un-HU_Hk?t=1421
–
W rozwiązaniu użyto algorytmu Find And Union który jest szczegółowo wyjaśniony w poniższym fragmencie:
https://youtu.be/KI7un-HU_Hk?t=2542
–
Poniżej kod wzorcowy do zadania użyty w powyższym omówieniu:
#include <bits/stdc++.h> using namespace std; const int MAX_FARMS = 1e5+7; int FAU[MAX_FARMS]; int Find (int a) { if ( FAU[a] == a ) return a; FAU[a] = Find ( FAU[a] ); return (FAU[a]); } void Union (int a, int b) { FAU[ Find(a) ] = FAU[ Find(b) ]; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); freopen("milkvisits.in", "r", stdin); freopen("milkvisits.out", "w", stdout); int number_of_farms, number_of_friends; string farms_milk_type; string solution; char required_milk_type; int farm1, farm2; int i; cin >> number_of_farms; cin >> number_of_friends; cin >> farms_milk_type; for (i=1; i<=number_of_farms; ++i) FAU[i] = i; for (i=1; i<number_of_farms; ++i) { cin >> farm1; cin >> farm2; if ( farms_milk_type[farm1-1] == farms_milk_type[farm2-1] ) { if ( Find (farm1) != Find (farm2) ) { Union (farm1, farm2); } } } for (i=0; i<number_of_friends; ++i) { cin >> farm1; cin >> farm2; cin >> required_milk_type; if ( Find (farm1) == Find (farm2) ) { if ( farms_milk_type[farm1-1] != required_milk_type ) { solution += '0'; continue; } } solution += '1'; } cout << solution; return 0; }