|
Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja
možete slati na e-mail:
tak.prog@gmail.com
U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.
|
logo by Igor Antolović
|
|
|
zadatak: Dalekovodi
|
U Bajtoviji Đurica je odlučio da uvede struju. Spojio je n kuća pomoću m dalekovoda različitog kvaliteta. Za svaki dalekovod se zna posle koliko sati neodržavanja zarđa i prestaje da provodi struju. Ispostavilo se da bi, kad bi pustio mrežu u rad, došlo do kratkog spoja i velike katastrofe. Zato je Đurica uposlio Dragančeta da ispita mrežu. Draganče je ispostavio Đurici izveštaj, u kome se nalazi spisak k parova kuća koje ne smeju međusobno da budu spojene (ni direktno dalekovodom, ni preko drugih kuća) da bi mreža smela da se pusti u rad. Đurica može da bira koje dalekovode će da nastavi da održava, a koje ne. Đurica vas je uposlio da odredite koliko najmanje sati mora da prođe da bi mogao da pusti mrežu u rad, a Dragančeta za teži deo posla, da ispita koje dalekovode da održava, a koje ne, na osnovu vašeg izveštaja.
Ulaz:
U prvom redu ulazne datoteke struja.in nalazi se prirodni brojevi n, m i k (1 ≤ n, k ≤ 10000, 1 ≤ m ≤ 100 000). U sledećih m redova nalaze se po tri broja i, j, kv koja označavaju da su kuće i i j spojene dalekovodom kvaliteta kv (1 ≤ kv ≤ 1 000 000 000, posle kv sati prestaje da propušta struju ako se ne održava). Zatim se u preostalih k redova nalazi po dva broja i i j, koja označavaju da kuće i i j ne smeju biti spojene, da bi mreža smela da se pusti u rad. Nijedan par gradova nije spojen direktno više od jednim dalekovodom, ni 2 puta naveden na Dragančetovom spisku.
Izlaz:
U izlaznu datoteku struja.out upisati minimalan broj sati s koji mora da prođe da bi mreža smela da se pusti u rad.
Primer:
struja.in
|
|
struja.out
|
7 8 3
1 2 5
1 4 8
3 2 3
4 3 2
4 5 3
5 6 6
5 7 3
6 7 9
2 5
1 3
5 7
|
|
6
|
Objašnjenje:
Opis dalekovoda iz ulaza odgovara dalekovodu prikazanom na slici iznad. Moguće je osposobiti mrežu za 6 sati, ako prestanu da se održavaju dalekovodi 1-2, 3-4, 5-6, 5-7
|
|
rešenje
|
Prvo treba primetiti da je zadatak moguće rešiti tako što se ne održava nijedan dalekovod, i da je potrebno izračunati posle koliko sati dati parovi kuća neće biti spojeni. Takođe treba primetiti da je potrebno posmatrati samo one sate u kojima bar jedan od dalekovoda prestaje da propušta struju. Proveru da li je posle nekog konkretnog sata moguće pustiti mrežu u rad, je moguće uraditi pomoću nalaženja komponetni povezanosti (pomoću DFS-a ili BFS-a), i provere da li neki par kuća, koje ne smeju biti povezane, pripada istoj komponenti povezanosti. A pronalaženje odgovarajućeg broja sati je moguće binarnom pretragom, po svim mogućim satima.
Složenost binarne pretrage je O(log m), složenost nalaženja komponenti povezanosti O(m + n) (ako se graf čuva preko lista povezanosti), i provera parova O(k), pa je složenost algoritma O ((m + n + k) * log m).
Pseudokod
// sat - sortiran niz svih satova u kojima se kvari neki dalekovod
// sat[l] - najmanji, sat[d] - najveci
while (d-l>1)
{
s=(l+d)/2;
if (moze(sat[s])
d=s;
else
l=s;
}
if (moze(sat[l]))
d=l;
write(sat[d])
dfs(int i,int komp,int kv)
{
ozn[i]=komp;
int j;
(za sve cvorove j povezane sa cvorom i granom veceg kvaliteta od kv)
if (ozn[j]==0)
dfs(j,komp,kv);
}
int moze(int s)
{
(postavi sve ozn na 0)
int i,komp=1;
(za sve cvorove i)
if (ozn[i]==0)
dfs(i,komp,s);
komp++;
int ind=1;
(za sve parove kuca kuca1 i kuca2, dok je ind==1)
ind=(ozn[kuca1]!=ozn[kuca2]);
return ind;
}
|
|
fajl: struja.cpp
|
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
const int maxn=41000;
const int maxm=110000;
typedef struct{
int p,q,kv;
} grana;
int kuca1[maxm],kuca2[maxm],sat[maxm],poc[maxn],ozn[maxn];
grana pov[2*maxm];
int n,m,k;
int upG(const void *px,const void *py)
{
grana *x=(grana *)px;
grana *y=(grana *)py;
if ((x->p)>(y->p)) return 1;
if ((x->p)<(y->p)) return -1;
if ((x->kv)<(y->kv)) return 1;
if ((x->kv)>(y->kv)) return -1;
if ((x->q)>(y->q)) return 1;
if ((x->q)<(y->q)) return -1;
return 0;
}
int upI(const void *px,const void *py)
{
int *x=(int *)px;
int *y=(int *)py;
if (*x>*y) return 1;
if (*x<*y) return -1;
return 0;
}
void dfs(int i,int b,int s)
{
ozn[i]=b;
int j;
for(j=poc[i];(j<poc[i+1]) && (pov[j].kv>s);j++)
if (!ozn[pov[j].q])
dfs(pov[j].q,b,s);
return;
}
int moze(int s)
{
memset(ozn,0,sizeof(ozn));
int i,j=1;
for(i=0;i<n;i++)
if (!ozn[i])
{dfs(i,j,s);j++;}
int ind=1;
for(i=0;(i<k)&&ind;i++)
ind=(ozn[kuca1[i]]!=ozn[kuca2[i]]);
return ind;
}
int main()
{
freopen("struja.in","r",stdin);
freopen("struja.out","w",stdout);
int i,j,l,d,s;
scanf("%d%d%d",&n,&m,&k);
for(i=0;i<m;i++)
{
scanf("%d%d%d",&(pov[2*i].p),&(pov[2*i].q),&(pov[2*i].kv));
pov[2*i].p--;pov[2*i].q--;
pov[2*i+1].p=pov[2*i].q;
pov[2*i+1].q=pov[2*i].p;
pov[2*i+1].kv=pov[2*i].kv;
sat[i+1]=pov[2*i].kv;
}
for(i=0;i<k;i++)
{
scanf("%d%d",&(kuca1[i]),&(kuca2[i]));
kuca1[i]--;kuca2[i]--;
}
qsort(pov,2*m,sizeof(grana),upG);
for(i=j=0;i<=n;i++)
{
while ((pov[j].p<i) && (j<2*m)) j++;
poc[i]=j;
}
sat[0]=0;
qsort(sat,m+1,sizeof(int),upI);
for(i=1,j=0;i<=m;i++)
{
if (sat[j]!=sat[i])
{
j++;
sat[j]=sat[i];
}
}
l=0;d=j;
while (d-l>1)
{
s=(l+d)/2;
if (moze(sat[s]))
d=s;
else
l=s;
}
if (moze(sat[l]))
d=l;
printf("%d\n",sat[d]);
return 0;
}
|
|
|