Omówienie zadania Milk Visit

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=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;
}


Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz