Zadanie
V Absurdistane majú už dlho v pláne postaviť novú sieť diaľnic. Ale viete, ako to chodí: každé štyri roky sú voľby, s ktorými príde nový minister dopravy. Ten vždy najprv preplánuje celú dialničnú sieť a potom už do konca volebného obdobia nič nestihne. Následne príde nový minister a taktiež nanovo prerobí celé plány. Predchádzajúci minister si však rok pred voľbami povedal, že túto tradíciu poruší a diaľnicu stavať naozaj začne. Lenže žiadnu cestu za rok nepostaví, a preto, aby po ňom niečo ostalo, rozhodol sa postaviť aspoň diaľničné križovatky.
Preto zobral svoje plány a náhodne z nich vybral pár miest kde sa do volieb postavili križovatky.
Po ňom však prišiel nový minister. Ten podľa zvyku staré plány zahodil a teraz má pred sebou tažkú úlohu: musí naplánovať celú diaľničnú sieť tak, aby dopĺňala už existujúce križovatky. Keďže chce mať v plánoch poriadok, určil si nasledujúce dva ciele: musí použiť čo najmenej rôznych diaľnic a všetky z nich musia ísť buď v severo-južnom alebo západo-východnom smere. Dokážete aj vy za takýchto podmienok zostrojiť nový plán diaľnic?
Úloha
Na vstupe dostanete zoznam všetkých diaľničných križovatiek postavených predchádzajúcim ministrom.
Vašou úlohou je navrhnúť diaľničnú sieť tak, aby obsahovala všetky tieto križovatky.
Cez každú križovatku musia prechádzať dve diaľnice (keď už je tam ten nadjazd, je to už vybudovaná diaľnica a teda ju nemožno zrušiť), môžu však byť akokoľvek krátke (stačí keď sa diaľnica končí hneď za nadjazdom). Žiadne dve diaľnice sa nemôžu križovať mimo križovatky (to by bolo divné, nie?). Nemôžete postaviť žiadnu novú križovatku, lebo na to nemáte financie.
Formát vstupu
Na prvom riadku vstupu sa nachádza číslo \(n\) – počet križovatiek. Na nasledujúcich \(n\) riadkoch sú vymenované jednotlivé križovatky. Na každom riadku sú súradnice \(1 \le x_i, y_i \le 10^9\): zemepisné súradnice jednotlivých križovatiek.
Formát výstupu
Na výstup vypíšte navrhnutú diaľničnú sieť. V prvom riadku vypíšte číslo \(H\): počet západo-východných diaľnic.
Potom vypíšte \(H\) riadkov. Na každom riadku vypíšte štyri čísla \(1 \le x_i, y_i, x'_i, y'_i \le 10^9\), ktoré reprezentujú západo-východnú diaľnicu. Musí platiť, že \(y_i = y'_i\).
V ďalšom riadku vypíšte číslo \(V\): počet severo-južných diaľnic. Potom vypíšte \(V\) riadkov. V každom riadku vypíšte štyri čísla \(1 \le x_i, y_i, x'_i, y'_i \le 10^9\), ktoré reprezentujú severo-južnú diaľnicu. Musí platiť, že \(x_i = x'_i\).
Hodnotenie
Je 8 sád vstupov. Platia v nich nasledovné obmedzenia:
Sada | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|
\(0 \leq n \leq\) | \(6\) | \(6\) | \(16\) | \(16\) | \(100\) | \(10\) | \(1\,000\) | \(1\,000\) |
\(0 \leq x_i, y_i \leq\) | \(6\) | \(10^9\) | \(16\) | \(10^9\) | \(100\) | \(10^9\) | \(1\,000\) | \(10^9\) |
Príklad:
Input:
4
2 1
2 3
1 2
3 2
Output:
3
1 1 2 1
1 2 3 2
1 3 2 3
4
1 2 1 2
3 1 3 3
2 1 2 1
2 3 2 3
Všimnite si, že viacero z diaľníc už nepokračuje mimo križovatku.
V diaľničnej sieti však musia byť, keďže v každej križovatke sa musia križovať diaľnice.
Na vstupe máme niekoľko diaľničných križovatiek. Naším cieľom je navrhnúť severojužné a západovýchodné diaľnice tak, aby:
- každá križovatka bola križovatkou dvoch diaľníc,
- aby sa žiadne dve diaľnice nekrižovali mimo križovatie,
- a aby bolo diaľníc čo najmenej.
Skúsme najprv ignorovať poslednú podmienku a pozrieť sa na riešenie iteratívne: Na začiatku máme veľa križovatiek a na každej z nich sa križujú dve samostatné diaľnice. Ak máme \(n\) križovatiek tak máme \(2n\) diaľníc. Chceme aby diaľníc bolo čo najmenej, preto chceme tieto diaľnice pospájať. Križovatku môžeme napojiť iba na tú ktorá je k nej najbližšia v každom zo štyroch smeroch. Každé takéto spojenie nám zníži počet diaľníc o jedna. Keby sme ignorovali druhú podmienku tak v podstate každú križovatku môžeme spojiť s najbližšími križovatkami vo všetkých štyroch smeroch a tým pádom by nám pre každú x-ovú súradnicu zostala práve jedna zvisĺa diaľnica a pre každú y-novú súradnicu zostala práve jedna vodorovná diaľnica.
Druhá podmienka však situáciu komplikuje. V praxi pre nás znamená že na každej križovatka spojníc diaľníc ktorá nie je na vstupe si musíme vybrať ktorú spojnicu ponecháme a ktorú nie. Toto nám však úlohu transformuje na vcelku štandartný grafový problém: Pre každú spojnicu majme jeden vrchol v grafe. Pre každú križovatku dvoch spojníc ktorá nie je na vstupe majme hranu ktorá spojí dva vrcholy reprezentujúce tieto dve spojnice. Teraz z grafu chceme vybrať čo najviac vrcholov (spojníc), tak aby žiadne dva vybrané vrcholy neboli spojené hranou. Chceme teda vybrať najväčšiu nezávislú množinu (maximum independent set).
Tento postup si môžme ozrejmiť aj na nasledovnom príkladnom obrázku. Na obrázku máme jednotlivé križovatky. Na začiatku sa v každej z nich stretávajú dve diaľnice. Keďže chceme počet diaľníc minimalizovať, chceme vybudovať ich spojnice, kde každá spojnica nám zníži počet jedinečných diaľníc o jedna. V ideálnom prípade chceme využiť všetky spojnice, ale v tomto prípade to nie je možné, keďže diaľnice sa nesmú križovať mimo križovatiek. Túto úlohu si pretransformujeme do bipartitného grafu, kde vrcholy reprezentujú spojnice. Hrany sú medzi vrcholmi práve vtedy keď sa dve spojnice križujú a teda nemôžeme postaviť obidve. Chceme teda vybrať čo najviac vrcholov tak aby medzi žiadnou dvojicou vybraných vrcholov nebola hrana.
Problém najväčšej nezávislej množiny v grafe je vo všeobecnosti v kategorí NP-úplných problémov a teda je pravdepodobné, že sa nám naň nikdy nepodarí nájsť riešenie v polynomiálnom čase. Náš graf má však užitočnú vlastnosť – je bipartitný. To znamená, že vrcholy v ňom vieme rozdeliť do dvoch kategoríi: severojužné spojnice a východozápadné spojnice, pričom hrany sú iba medzi vrcholmi z rôznych kategórii. Tento problém už má známe riešenie, ktoré sme sa pokúsili zhrnúť tu. Časová zložitosť pre riešenie tohto problému je \(O(E \sqrt {V})\), pre bipartitný graf s \(E\) hranami a \(V\) vrcholmi ak hľadáme maximálne párovanie pomocou Edmonds–Karp. V našom prípade však absolútne postačí pomalší algoritmus na hľadanie párenia s časovou zložitosťou \(O(EV)\). Keď máme križovatiek \(n\), tak môže byť medzi nimi \(4n \in O(n)\) spojníc. Tieto spojnice sa však môžu krížiť pomerne veľa krát. Napríklad na obrázku nižšie vidíme situáciu v ktorej máme až \((n/4)^2 \in O(n^2)\) križovatiek spojníc. Viac ich však nemôže byť, keďže \(4 n\) spojníc sa môže križovať najviac v \(16n^2 \in O(n^2)\) miestach. Tým pádom je časová zložitosť výsledného riešenia \(O(E \sqrt {V}) = O(n^2 \sqrt {n}) = O(n^{2.5})\). Pamäťová zložitosť je \(O(n^2)\), keďže potrebujeme vyrobiť graf všetkých hrán (krížení spojníc).
#include <iostream>
#include <vector>
#include <tuple>
#include <map>
#include <algorithm>
#include <cstdio>
#include <set>
using namespace std;
#define FOR(i,n) for(int i = 0; i<(n); ++i)
bool dfs(int a, int vrstva, vector<vector<int>>& G, vector<int>& z_b_do_a, vector<int>& A, vector<int>& B) {
if (A[a] != vrstva) return 0;
[a] = -1;
Afor (int b : G[a]) if (B[b] == vrstva + 1) {
[b] = 0;
Bif (z_b_do_a[b] == -1 || dfs(z_b_do_a[b], vrstva + 1, G, z_b_do_a, A, B))
return z_b_do_a[b] = a, 1;
}
return 0;
}
int hopcroftKarp(vector<vector<int>>& G, vector<int>& btoa) {
int res = 0;
<int> A(G.size()), B(btoa.size()), terajsia_vrstva, dalsia_vrstva;
vectorwhile (true) {
//polia A a B budu obsahovat vzdialenost po striedavych cestach z nesparovanych vrcholov v A
(A.begin(), A.end(), 0);
fill(B.begin(), B.end(), 0);
fill/// Najdenie nesparovanych vrcholov v A
.clear();
terajsia_vrstva// -1 su sparovane vrcholy v A
for (int a : btoa) if(a != -1) A[a] = -1;
(a, G.size()) if(A[a] == 0) terajsia_vrstva.push_back(a);
FOR//
for (int vrstva = 1; true; vrstva++) {
bool posledna = false;
.clear();
dalsia_vrstvafor (int a : terajsia_vrstva) for (int b : G[a]) {
if (btoa[b] == -1) {
//nasli sme zlepsujucu cestu
[b] = vrstva;
B= true;
posledna }
else if (btoa[b] != a && !B[b]) {
//tento vrchol je uz sparovany a teda haladame alternujucu cestu cez jeho sparovanu hranu
[b] = vrstva;
B.push_back(btoa[b]);
dalsia_vrstva}
}
if (posledna) break;
//nenasli sme zlepsujucu cestu ale nie je kam pokracovat teda mame maximalne parenie
if (dalsia_vrstva.empty()) return res;
for (int a : dalsia_vrstva) A[a] = vrstva;
.swap(dalsia_vrstva);
terajsia_vrstva}
/// Use DFS to scan for augmenting paths.
(a, G.size())
FOR+= dfs(a, 0, G, btoa, A, B);
res }
}
//najde vrcholove pokrytie, vyuziva minimalne parenie
<int> vrcholove_pokrytie(vector<vector<int>>& g, int A, int B) {
vector<int> z_b_do_a(B, -1);
vectorint res = hopcroftKarp(g, z_b_do_a);
<bool> X(A, true), Y(B);
vector
//oznaci vrcholy, ktore su sparene, ako tie, ktore zatial nie su v X, vsetky ostatne su v X0
for (int b : z_b_do_a) if (b != -1) X[b] = false;
// kedze nam nezalezi na poradi vrcholov pocas vyhladavania (chceme iba najst vrcholy v X), tak mozeme namiesto fronty pouzit vector ako stack
<int> q, C;
vector// na zaciatku do stacku prehladavanych vrcholov pridame vrcholy z X_0
for(int i=0; i<A; i++) if (X[i]) q.push_back(i);
while (!q.empty()) {
int a = q.back(); q.pop_back();
// pridame vrchol a do X
[a] = true;
Xfor (int b : g[a]) if (!Y[b] && z_b_do_a[b] != -1) {
// ak sme vrchol b doteraz nevideli a je spareny, tak ho pridame do Y
// ak je spareny, tak sa uz nechceme vracat po hrane, v ktorej sme uz boli
[b] = true;
Y.push_back(z_b_do_a[b]);
q}
}
// na zaver precislujeme vrcholy napravo a vratime vector vrcholov v najmensom vrcholovom pokryti
for(int i = 0; i < A; i++) if (!X[i]) C.push_back(i);
for(int i = 0; i < B; i++) if (Y[i]) C.push_back(A + i);
return C;
}
long long getn() {
long long x;
("%lld",&x);
scanfreturn x;
}
typedef tuple<int,int, bool> dialnicny_usek;
int main() {
<int, map<int, int>> YX;
map<int, map<int, int>> XY;
map<int, map<int, int>> krdole;
map<int, map<int, int>> krdoprava;
mapint n = getn();
(i,n) {
FORint x=getn();
int y=getn();
[y][x]=i;
YX[x][y]=i;
XY}
//zlava doprava
<vector<dialnicny_usek> > nechcene_krizenia;
vector<dialnicny_usek, int> mapa_zvislych_usekov, mapa_vodorovnych_usekov;
mapfor (const auto &it1: YX)
{
int y = it1.first;
for (const auto &it2: XY) {
int x = it2.first;
auto it = it2.second.lower_bound(y);
auto it_pred_x = it1.second.lower_bound(x);
if(it->first != y && it!=it2.second.begin() && it != it2.second.end()
&& it_pred_x->first != x && it_pred_x != it1.second.begin() && it_pred_x != it1.second.end())
{
//x y zvisly?
auto it3= it1.second.lower_bound(x);
.push_back({{x, it->first, true}, {it3->first, y, false}});
nechcene_krizenia[{x, it->first, true}] = 0;
mapa_zvislych_usekov[{it3->first, y, false}] = 0;
mapa_vodorovnych_usekov}
}
}
<dialnicny_usek> pole_zvislych_usekov;
vectorfor (auto &usek : mapa_zvislych_usekov) {
.second = pole_zvislych_usekov.size();
usek.push_back(usek.first);
pole_zvislych_usekov}
<dialnicny_usek> pole_vodorovnych_usekov;
vectorfor (auto &usek : mapa_vodorovnych_usekov) {
.second = pole_vodorovnych_usekov.size();
usek.push_back(usek.first);
pole_vodorovnych_usekov}
<vector<int> > nechcene_krizenia_graf(pole_zvislych_usekov.size());
vectorfor (auto &krizenie : nechcene_krizenia) {
[mapa_zvislych_usekov[krizenie[0]]].push_back(mapa_vodorovnych_usekov[krizenie[1]]);
nechcene_krizenia_graf}
<int> cov = vrcholove_pokrytie(
vector,
nechcene_krizenia_graf.size(),
nechcene_krizenia_graf.size());
pole_vodorovnych_usekov
<dialnicny_usek> nepostavime;
setfor (int i : cov) {
;
dialnicny_usek dif (i < mapa_zvislych_usekov.size()) {
= pole_zvislych_usekov[i];
d } else {
= pole_vodorovnych_usekov[i - mapa_zvislych_usekov.size()];
d }
.insert(d);
nepostavime}
<vector<int> > vodorovne_dialnice, zvisle_dialnice;
vector
for (const auto &it1: YX)
{
//hladame po riadkoch vodorovne dialnice
int y = it1.first;
auto it_next = it1.second.begin();
int x_zac = -1;
for (auto it2 = it_next++; ; it2 = it_next++) {
if (x_zac == -1) {
= it2->first;
x_zac }
// ak uz dalej ziadna krizovatka nie je tak dialnicu skoncime
bool skonci = it_next == it1.second.end();
//skoncime ju aj ked dalsi usek sa nam neoplati postavit
if(!skonci)
{
= {it_next->first, y, false};
dialnicny_usek usek = nepostavime.count(usek);
skonci }
//ked skoncime tak sme nasli koniec a ten si zapiseme
if (skonci)
{
.push_back({x_zac, y, it2->first, y});
vodorovne_dialnice= -1;
x_zac }
if (it_next == it1.second.end()) break;
}
}
for (const auto &it1: XY)
{
//hladame po stlpcoch zvisle dialnice
int x = it1.first;
auto it_next = it1.second.begin();
int y_zac = -1;
for (auto it2 = it_next++; ; it2 = it_next++) {
if (y_zac == -1) {
= it2->first;
y_zac }
// ak uz dalej ziadna krizovatka nie je tak dialnicu skoncime
bool skonci = it_next == it1.second.end();
//skoncime ju aj ked dalsi usek sa nam neoplati postavit
if(!skonci)
{
= {x, it_next->first, true};
dialnicny_usek t = nepostavime.count(t);
skonci }
//ked skoncime tak sme nasli koniec a ten si zapiseme
if (skonci)
{
.push_back({x, y_zac, x, it2->first});
zvisle_dialnice= -1;
y_zac }
if (it_next == it1.second.end()) break;
}
}
("%d\n", vodorovne_dialnice.size());
printffor(auto x: vodorovne_dialnice)
("%d %d %d %d\n", x[0], x[1], x[2], x[3]);
printf("%d\n", zvisle_dialnice.size());
printffor(auto x: zvisle_dialnice)
("%d %d %d %d\n", x[0], x[1], x[2], x[3]);
printf
}
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.