Текущ брой на Списание ИнфоМан
 


Турнир за Купата на Декана - 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;
}


Автори: Веселин Георгиев и Красимир Добрев


обратно към текущ брой