Финален (подборен) кръг от националната
олимпиада по информатика - София 1999
тема 8-11 клас
Ден 1, Зад. 2 - ФИРМЕНИ БАЗИ (30 точки)
Фирма продава компютри в N града (3N35), номерирани с числата 1, 2, …, N. Между M двойки от тези градове има директни пътища. Ръководството на фирмата иска да изгради фирмени бази за гаранционно обслужване на продаваната техника в някои от градовете, но така че за всеки град Х да съществува база – или в Х, или в някой от съседите му (до които от Х има директен път). Съставете програма BAS.EXE, която намира минималният брой бази, които фирмата трябва да изгради за да е изпълнено горното условие.
ВХОДЪТ се чете от текстов файл BAS.INP. В първия ред са зададени броят на градовете N и броя M на двойките градове, свързани с директни пътища, разделени с един интервал. Всеки от следващите M реда съдържа по два номера на градове, свързани с директен път, разделени с по един интервал.
ИЗХОДЪТ на програмата се записва в текстов файл BAS.OUT, в единствения ред на който се извежда полученият резултат.
ПРИМЕР:
Вход Изход
8 12 2
1 2
1 6
1 8
2 3
2 6
3 4
3 5
4 5
4 7
5 6
6 7
6 8
Решение:
Можем да разглеждаме градовете като върхове на граф, а пътищата като ребра. Тогава задачата ще се състой в намирането на МИНИМАЛНО-ДОМИНИРАЩО МНОЖЕСТВО в неориетиран граф, което е NP-пълна задача.
Доминиращо множество
в граф G(V,E) се нарича такова подмножество SV, че всички върхове, които не са от S, са съседни на от някой връх от S.Едно доминиращо множество се нарича
минимално, ако не съдържа в себе си друго доминиращо множество.Търсим минимално МИНИМАЛНО-ДОМИНИРАЩО МНОЖЕСТО. Т.е МИНИМАЛНО-ДОМИНИРАЩО МНОЖЕСТВО с минимален брой върхове. Навсякъде по долу под МИНИМАЛНО-ДОМИНИРАШО МНОЖЕСТВО да се рабира МИНИМАЛНО-ДОМИНИРАШО МНОЖЕСТВО(мин.дом.множ) с минимален брой върхове.
Ще използваме метода на backtraking за решаването на задачата.
За по-голямо бързодействие ще разделим графа на свързани компоненти, като за всяка компонента ще намираме МИНИМАЛНОТО-ДОМИНИРАЩО МНОЖЕСТВО, за дадената компонента.
За целта ще използваме масива g – като g[i][j] ще е 0 или 1 в зависимост от това дали има ребро от i до j. Понеже графа е неориентиран, тогава тази матрица ще е транспонирана, т.е g[i][j] = g[j][i].
В масива comp, ще съхраняваме една свързана компонента, като comp[i] = 1, ako i участва в текущо разглежданата компонента. В масива used – ще съхраняваме вече разгледаните върхове, а във масива taken – "взетите" върхове от "backtraking-a".
И така решението ще изглежда по следния начин:
Вход.
for (за всяка компонента) {
solveComponent();
bestSol += best;
}
Изход на bestSol
като в best се пази броя на върховете които участват в мин.дом.множ. за дадената свързана компонента, а solveComponent() ще намира мин.дом.множ. за текущата компонента.
Остана да разгледнаме само solveComponent().
solveComponent() се състой от рекурсивната функция rec, която на всяка стъпка избира по един свободен връх t, след което за всeки инцидентен на него връх i извършваме следното:
Маркиране t като зает. Маркираме всички инциденти на i, като заети ("покриваме ги") . След което "задълбаваме в рекурсията".
rec() ще изглежда така:
rec() {
t = първия свободен (непокрит) връх.
Ако t == 0 сме намерили едно доминиращо множество и проверяваме дали е минимално.
Иначе {
За i, такова че g[i][t] = 1 {
Покриваме i, т.е маркираме всички съседи на i, като заети.
rec().
Премахваме покритието на i.
}
}
}
Програма:
#include <stdio.h>
#include <mem.h>
unsigned int n, m; // n - vert m - edges
unsigned char g[40][40]; // graph
unsigned char comp[40]; // one component
unsigned char used[40]; // for dfs
unsigned char taken[40]; // for components;
unsigned int best, curr;
void init() {
memset(g, 0, sizeof(g));
}
void readIt() {
unsigned int p,q,i;
FILE *F;
F = fopen("BAS.INP", "rt");
fscanf(F, "%d%d", &n, &m);
for (i=0; i<m; i++) {
fscanf(F, "%d%d", &p, &q);
g[p][q] = g[q][p] = 1;
}
for (i=1; i<=n; i++)
g[i][i] = 1;
fclose(F);
}
void dfs(unsigned int v) {
unsigned int i;
comp[v] = 1;
used[v] = 1;
for (i=1; i<=n; i++)
if (!used[i] && g[v][i]) {
dfs(i);
}
}
void take(unsigned int k) {
unsigned int i;
for (i=1; i<=n; i++)
taken[i] += g[k][i];
}
void untake(unsigned int k) {
unsigned int i;
for (i=1; i<=n; i++)
taken[i] -= g[k][i];
}
void rec() {
unsigned int takeMe=0, i;
for (i=1; i<=n; i++)
if (taken[i]==0 && comp[i]==1) {
takeMe = i;
break;
}
if (takeMe == 0) {
if (curr < best) best = curr;
return;
}
for (i=1; i<=n; i++)
if (g[i][takeMe]) {
curr++;
take(i);
if (curr < best) rec();
untake(i);
curr--;
}
}
void solveComponent() {
memset(taken, 0, sizeof(taken));
curr=0; best=n+1;
rec();
}
void solve() {
unsigned int bestSol=0, i;
FILE *f;
memset(used, 0, sizeof(used));
for (i=1; i<=n; i++)
if (!used[i]) {
memset(comp, 0, sizeof(comp));
dfs(i);
solveComponent();
bestSol += best;
}
f = fopen("BAS.OUT", "wt");
fprintf(f, "%d\n", bestSol);
fclose(f);
}
void main() {
init();
readIt();
solve();
}
Васил Поповски
студент - СУ