Турнир за Купата на Декана - 2005, Задача C
Уловието на задачата може да прочетете
тук.
Решение
Задачата се разделя на две части. В първата част се
преброяват срещанията на всяка буква в бележката, която трябва да се напише и
броят на ненаредените двойки (X,Y), където буквата X е отпечатана на гърба на буквата Y. Ако на гърба на дадена буква няма
отпечатан символ приемаме, че е отпечатан някакъв специален, който не
съществува първоначално в азбуката. Нека
ci
е броят на срещанията на буквата i
в желаната бележка, а cij е броят на двойките (i,
j).
Във втората част на задачата се построява претеглен ориентиран
граф G(V, E). V= {source, target} U {X | X е буква от латинската азбука}U {(X,Y) | X и Y са букви от латинската азбука или специалният символ}. Ребрата на графа са следните:
·
за
всяка буква X, реброто (source, X) има капацитет cx.
·
за
всяка двойка (X,Y), реброто ((X,Y), target) има капацитет cxy
.
·
за
всяка буква X
ребрата (X, (X,Y)) и (X, (Y,X)) имат капацитет c
x, където Y е произволна латинска буква или специален символ.
Пресмята се стойността на максималния поток от source
до target в така построеният граф G(V, E).
Бележката може да се конструира от списанието, тогава и само тогава, когато
стойността на потока е равна на сумата на cx
за всяка латинска буква X.
Графа може да се построи по друг начин като се използват
по-малко върхове. Отново има върхове, които се обозначават като source
и sink.
Потока се пуска от source
върха и стига в sink
върха. Междинно има три
реда върхове. Нека ги обозначим като редове от ред 0, ред 1 и ред 2. На редове 0,
1 и 2 всеки връх отговаря на буква от азбуката, но има и един връх за
специалният символ, който беше дефиниран по-горе. Ред 0 отговаря за символите
от съобщението, което трябва да се конструира. Ред 1 отговаря за символите,
които са на четни страници, а ред 2 за тези на нечетни. Ще обозначим върховете
в графа по следният начин: r0[x], r1[x], r2[x]. x е
някакъв символ. r1[
‘a’]
обозначава върха на ред
1, който отговаря на символа ‘a’. Нека графа е пълен и в началото всички ребра са с
пропускливост 0. За всяко срещане на символ в дадения текст се увеличава пропускливостта
на реброто от source към съответният връх на ред 0 с 1. След това се разглеждат
последователно символите по страниците. Ако се разглежда четна страница се
увеличават ребрата между върховете r0[x] и r1[x],
r
1[x] и r2[y], r0[y] и r1[x]. x е
символа, който се разглежда в момента на четната страница, а y е символа от другата му страна. Ако
разглежданата страница е нечетна се увеличава реброто между върховете r2[x]
и sink.
В този граф се намира
максимален поток. За да може да се изпише съобщението е нужно този поток да е
равен на броя букви в съобщението.По-долу е приложена реализация на втория подход.
Примерна реализация
#include <stdio.h>
#include <vector>
#include <string>
#include <iostream>
using namespace std;
struct node {
int dest, vol;
};
int p, h, w;
const int src = 0;
const int sink = 1;
int _fng(char c)
{
if (c >= 'A' && c <= 'Z') return c-'A';
return 26;
}
#define MAXS 10000000
#define msg(x) (_fng(x)+2)
#define pg1(x) (_fng(x)+28)
#define pg2(x) (_fng(x)+55)
#define ppg(a,x) (28 + (a)*27 + _fng(x))
int G[128][128];
char buff[MAXS];
int ds[128];
int ps[128];
int pr[128];
#define imin(a,b) ((a)<(b)?(a):(b))
int augment(void)
{
memset(ds, 0, sizeof(ds));
memset(ps, 0, sizeof(ps));
memset(pr, -1, sizeof(pr));
ds[src] = 999666111;
while (1) {
int bi, mdist=0;
bi = -1;
for (int i = 0; i < 128; i++)
if (!ps[i] && ds[i] > mdist) {
mdist = ds[i];
bi = i;
}
if (bi == -1) return 0;
if (bi == sink) return ds[bi];
ps[bi] = 1;
for (int i = 0; i < 128; i++) {
if (!ps[i] && ds[i] < imin(ds[bi], G[bi][i])) {
pr[i] = bi;
ds[i] = imin(ds[bi], G[bi][i]);
}
}
}
}
int flow(void)
{
int all = 0;
int x;
int cf;
while (1) {
cf = augment();
if (cf == 0) break;
all += cf;
x = sink;
while (x != 0) {
G[pr[x]][x] -= cf;
G[x][pr[x]] += cf;
x = pr[x];
}
}
return all;
}
int main(void)
{
int t;
scanf("%d", &t);
while (t--) {
cin >> p >> h >> w;
memset(G, 0, sizeof(G));
vector<string> book;
for (int pg = 0; pg < p; pg++) {
for (int row = 0; row < h; row++) {
string s;
cin >> s;
while (s.length() < w)
s+=' ';
book.push_back(s);
}
}
if (pg % 2) {
string s;
for (int i = 0; i < w; i++)
s += ' ';
for (int i = 0; i < h; i++)
book.push_back(s);
}
string m;
cin >> m;
int hist[26] = {0};
for (int i = 0; i < m.length(); i++) {
G[src][msg(m[i])]++;
hist[_fng(m[i])]++;
}
for (int pg = 0; pg < p; pg++) {
for (int row = 0; row < h; row++) {
for (int col = 0; col < w; col++) {
char c1 = book[pg*h + row][col];
if (pg % 2 == 0) {
char c2 = book[(pg+1)*h+row][w-1-col];
G[msg(c1)][pg1(c1)] ++;
G[pg1(c1)][pg2(c2)] ++;
G[msg(c2)][pg1(c1)] ++;
}
if (pg % 2 == 1) {
G[pg2(c1)][sink] ++;
}
}
}
}
int res = flow();
if (res < m.length())
printf("NO\n");
else
printf("YES\n");
}
return 0;
}
Автори: Веселин Георгиев и Красимир Добрев
обратно към текущ брой
|