Февруарско състезание на USACO, 2005, Задача GOLD2. Secret Milking Machine
Условието на задачата може да прочетете
тук.
Решение
Тук ще разгледаме две различни решения на задачата
които са доста поучителни. Първото решение се базира на алгоритъма на Дейкстра
и донякъде на алгоритмите за намиране на максимален поток. Алгоритъмът ще се
опитва да намери Т различни един от
друг минимални пътя от първия до последния връх в графа. Алгоритъмът на
Дейкстра ще ни намира път минимален по най – голямото ребро в него, който минава
само през неизползвани досега в друг път ребра или ребра използвани но в
обратната посока. При успешно намиране на път трябва всички ребра по които
минаваме за първи път да отбележим като използвани, а тези, по които сме минавали и
преди, но в
другата посока, да ги отбележим като неизползвани и в двете посоки. И така
най-голямото ребро в Т-тия път, който намерим, е търсеният отговор. За да
разберете защо този алгоритъм работи трябва да сте запознати с алгоритмите за
намиране на максимален поток. За съжаление това решение, реализирано с
приоритетна опашка към алгоритъма на Дейкстра, е твърде бавно на един от
тестовете.
Второто решение на задачата се базира на двоичното
търсене. Ако сортираме ребрата в графа по тегло, то можем да направим двоично
търсене по тези ребра и така да определим най – голямото ребро което ще участва
в нашите Т пътя в графа. По-точно ако
изберем реброто на място midв сортирания списък на ребрата и пробваме да
построим Т различни пътя между
върховете 1 и Nв графа, ползвайки само ребра с
тегло по–малко или равно на теглото на реброто с индекс mid. Ако успеем, то следва да търсим
такова “гранично” ребро някъде над mid, а в противен случай – под mid. Това решение, за което ми каза
Светослав Колев, за съжаление, въпреки многото реализирани оптимизации, също е
твърде бавно на един тест (същия 6-ти
тест).
Примерна реализация:
/*
PROG:secret
LANG:C++
*/
# include <stdio.h>
# include <stdlib.h>
# include <limits.h>
# define MAXN 205 // константа за броя на върховете
# define MAXM MAXN*MAXN // константа за броя на ребрата
# define max(a,b) (((a)>(b))? (a):(b))
struct node{
int y, d, other; // .y - съседния връх .d - теглото на
// реброто, .other - посочва къде е обратното ребро на това.
};
node *data[MAXN]; // списък на съседство
char *used[MAXN]; // отбелязваме дали дадено
// ребро е използвано - 1 ако не е 0
int h[MAXN], hpos[MAXN], hlen; // масиви за приоритетната
// опашка h[] - самата питамида hpos[] - къде се намира даден елемент в h[]
int dist[MAXN]; // тук пазим разстоянията от
// началния връх до всички останали
int br[MAXN]; // br[i] - броя на съседите които има i-тия връх
int buf[MAXM][3]; // буферен масив за входа
int n, m, t, ans;
void readf() {
// четене на входа
freopen("secret.in","r",stdin);
freopen("secret.out","w",stdout);
scanf("%d%d%d",&n,&m,&t);
for ( int i=0 ; i<m ; i++ ) {
scanf("%d%d%d",&buf[i][0],&buf[i][1],&buf[i][2]);
br[buf[i][0]]++;
br[buf[i][1]]++;
}
// заделяне на памет за представянето на графа
for ( int i=1 ; i<=n ; i++ ) {
data[i] = (node *)malloc(br[i]*sizeof(node));
used[i] = (char *)malloc(br[i]*sizeof(char));
br[i] = 0;
}
// строене на графа
for ( int i=0 ; i<m ; i++ ) {
data[buf[i][0]][br[buf[i][0]]].y = buf[i][1];
data[buf[i][0]][br[buf[i][0]]].d = buf[i][2];
data[buf[i][1]][br[buf[i][1]]].y = buf[i][0];
data[buf[i][1]][br[buf[i][1]]].d = buf[i][2];
data[buf[i][0]][br[buf[i][0]]].other = br[buf[i][1]];
data[buf[i][1]][br[buf[i][1]]].other = br[buf[i][0]];
used[buf[i][1]][br[buf[i][1]]] = 0;
used[buf[i][0]][br[buf[i][0]]] = 0;
br[buf[i][0]]++; br[buf[i][1]]++;
}
}
// функции на приоритетната опашка
void siftup(int p) {
int pp = (p-1)/2; int buf = h[p];
while ( p>0 && dist[buf]<dist[h[pp]] ) {
h[p] = h[pp];
hpos[h[p]] = p;
p = pp;
pp = (pp-1)/2;
}
h[p] = buf;
hpos[h[p]] = p;
}
void push(int v) {
h[hlen] = v;
hpos[v] = hlen++;
siftup(hpos[v]);
}
void siftdown(int p) {
int pp = 2*p+1; int buf = h[p];
while ( pp+1<hlen && (
dist[buf]>dist[h[pp]] ||
dist[buf]>dist[h[pp+1]] ) ) {
if ( dist[h[pp]]< dist[h[pp+1]] ) {
h[p] = h[pp];
hpos[h[p]] = p;
p = pp;
pp = 2*pp+1;
} else {
h[p] = h[pp+1];
hpos[h[p]] = p;
p = pp+1;
pp = 2*p+1;
}
}
if ( pp<hlen && dist[buf]>dist[h[pp]] ) {
h[p] = h[pp];
hpos[h[p]] = p;
p = pp;
pp = 2*pp+1;
}
h[p] = buf;
hpos[h[p]] = p;
}
int pop() {
int result = h[0];
if ( hlen==0 ) return -1;
hpos[h[0]] = -1;
h[0] = h[hlen-1];
hpos[h[0]] = 0;
hlen--;
siftdown(0);
return result;
}
// алгоритъма на Дейкстра
int dijkstra() {
int usedv[MAXN], m[MAXN], edge[MAXN]; // usedv[] - отбелязва
// дали сме определили разстоянието да даден връх
// m[] - отбелязваме кой връх сме дошли в дадения
// edge[] - отбелязваме кое ребро сме ползвали
// за да дойдем в даден връх
int next;
// инициализация
for ( int i=0 ; i<MAXN ; i++ ) {
dist[i] = INT_MAX;
usedv[i] = 0;
hpos[i] = -1;
}
hlen = 0;
dist[1] = 0;
next = 1;
// същина
do {
usedv[next] = 1;
for ( int i=0 ; i<br[next] ; i++ ) {
if ( !used[next][i] && !usedv[data[next][i].y] &&
dist[data[next][i].y]>max(dist[next],data[next][i].d) ) {
dist[data[next][i].y] = max(dist[next],data[next][i].d);
m[data[next][i].y] = next;
edge[data[next][i].y] = i;
if ( hpos[data[next][i].y] == -1 ) {
push(data[next][i].y);
} else {
siftup(hpos[data[next][i].y]);
}
}
}
next = pop();
if ( next == -1 ) {
printf("-1\n");
exit(0);
}
}while(next != n);
// обработване на намерения път
int v=n;
while (v != 1 ) {
if ( used[v][data[m[v]][edge[v]].other] ) {
used[v][data[m[v]][edge[v]].other] = 0;
} else {
used[m[v]][edge[v]] = 1;
}
v = m[v];
}
return dist[n];
}
void solve() {
// последователно пускане
// на t алгоритъма на Дейкстра
int len;
for ( int i=0 ; i<t ; i++ ) {
len = dijkstra();
if ( ans<len ) {
ans = len;
}
}
printf("%d\n",ans);
}
int main() {
readf();
solve();
return 0;
}
Автор: Никола Борисов
обратно към брой 27
|