Tävlingsprogrammering/Uppgifter/Vägspärrar
Vägspärrar
Polisen håller på att introducera ett nytt system som ska underlätta bovjakten. Området som täcks av polisen består av N städer med E vägar (dubbelriktade) som sammanbinder dem. Städerna numreras från 1 till N.
Polisen vill ofta fånga tjuvarna när de tar sig från en stad till en annan. Polisledningen kollar på kartan och försöker komma underfund med var de ska sätta upp barrikader och vägspärrar. Deras nya system behöver kunna svara på följande typer av frågor:
Betrakta två städer A och B, och en väg som sammanbinder städerna G1 och G2. Kan bovarna ta sig från stad A till stad B om denna väg blockeras så att bovarna inte kan använda den? Betrakta tre städer A, B och C. Kan bovarna ta sig från A till B om hela staden C tas bort och bovarna inte kan komma in i staden? Skriv ett program som implementerar systemet ovan.
Indata
Den första raden innehåller två heltal N och E (2 ≤ N ≤ 100 000, 1 ≤ E ≤ 500 000), antalet städer och vägar.
De följande E raderna beskriver vägarna och innehåller två olika heltal mellan 1 och N - numret på de städer som vägen går mellan. Det kommer högst finnas en väg mellan två givna städer.
Därefter följer en rad med två heltal Q (1 ≤ Q ≤ 300 000), antalet frågor som systemet ska testas med, samt talet T (1 eller 2) som anger vilken typ av fråga de Q frågorna är.
De följande Q raderna innehåller antingen tre eller fyra heltal, beroende på T ovan.
Om frågetypen är 1, innehåller raderna 4 heltal A, B, G1 och G2, beskrivna ovan. A och B kommer att vara olika, och G1 och G2 kommer att beskriva en existerande väg.
Om frågetypen är 2, innehåller raderna 3 heltal A, B och C, beskrivna ovan. Dessa tre tal kommer att skilja sig åt.
Testdatat kommer vara konstruerat så att det går att ta sig mellan varje par av städer om inga vägspärrar sätts upp.
Utdata
Skriv ut en rad per fråga. Svaret på en fråga är antingen "ja" eller "nej".
Bedömning
I 50% av testfallen kommer T vara 1. I 20% av testfallen gäller följande: N ≤ 1000, E ≤ 5000, Q ≤ 100.
Exempel 1: Indata
13 15 1 2 3 5 2 4 2 6 7 10 1 4 1 7 2 3 7 8 9 12 7 9 8 11 4 6 8 12 12 13 5 1 5 13 1 2 6 2 1 4 13 6 7 8 13 5 7 1 12 8 12 8
Exempel 1: Utdata
ja ja ja nej ja
Exempel 2: Indata
13 15 1 2 3 5 2 4 2 6 7 10 1 4 1 7 2 3 7 8 9 12 7 9 8 11 4 6 8 12 12 13 5 2 13 6 7 13 6 8 1 5 2 10 6 1 10 6 4
Exempel 2: Utdata
nej ja nej nej ja
Lösning[redigera]
Detta var den klart svåraste uppgiften i KATT-2. Den enkla, "naiva", lösningen som för varje query gör en komplett grafsökning ger endast 20 eller 30 poäng. För att få full poäng behöver indatat preprocessas på ett sådant sätt att varje query kan svaras på blixtsnabbt. Denna preprocessering kan man göra med en DFS sökning, med en algoritm som liknar den för att hitta en grafs "artikulationspunkter" och "broar" (se t ex http://www.cse.ohio-state.edu/~lai/780/9.graph.pdf)
Utan att gå in i detalj allt för mycket, så samlar vi in följande tal för varje nod i grafen när vi gör DFS-sökningen (som kan börja på godtycklig nod):
- Upptäckstid - ett diskret tidsindex när vi började processera noden
- Avslutningstid - tidsindex när noden är färdigprocesserad
- Djup - nodens djup i DFS-trädet
- lowlink - den nod med lägst upptäckstid som kan nås från den nuvarande noden eller från någon av dess avkomlingar (via en enstaka tillbakakant)
Dessa tal låter oss skapa följande två användbara funktioner:
- is_descendent(A, B) - är nod A i subträdet rotat vid B
- find_related_child(A, B) - när A är i B's subträd, finn det barn till B så att A är avkomling till det barnet (med andra ord, om B har flera barn, find det vars subträd A tillhör)
Med dessa funktioner kan queries av båda typen svaras på genom att betrakta ett antal olika fall. Se koden nedan för detaljer.
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cassert>
using namespace std;
int n, m;
struct edge {
int u, v;
edge (int U, int V) { u = U; v = V; }
};
bool operator< (const edge &A, const edge &B) { return A.u < B.u; }
struct sparse_graph {
vector<edge> E;
vector< vector<edge>::iterator > V;
void insert_edge(const edge &e) {
E.push_back(e);
}
void init() {
V.resize(n+1);
sort(E.begin(), E.end());
V[0] = E.begin();
for(int i = 1; i <= n; ++i)
for(V[i] = V[i-1]; V[i] != E.end() && V[i]->u < i; ++V[i]);
}
inline vector<edge>::iterator begin( int u ) { return V[u]; }
inline vector<edge>::iterator end( int u ) { return V[u+1]; }
} graph;
vector<int> discover, finish, lowlink, depth;
int Time = 0;
vector< vector<int> > children;
void dfs(int u, int dad, int d) {
discover[u] = lowlink[u] = Time++;
depth[u] = d;
for(vector<edge>::iterator it = graph.begin(u); it != graph.end(u); ++it) {
if (it->v == dad) continue;
if (discover[it->v] == -1 ) {
dfs(it->v, u, d+1);
lowlink[u] = min(lowlink[u], lowlink[it->v]);
children[u].push_back(it->v);
} else {
lowlink[u] = min(lowlink[u], discover[it->v]);
}
}
finish[u] = Time++;
}
int is_descendant(int a, int b) {
return discover[b] <= discover[a] && finish[a] <= finish[b];
}
int find_related_child(int me, int descendant) {
int lo = 0, hi = children[me].size() - 1;
if (hi < 0) {printf("error\n"); }
while (lo != hi) {
int mid = (lo+hi) / 2;
if (discover[descendant] > finish[children[me][mid]])
lo = mid+1;
else if (finish[descendant] < discover[children[me][mid]])
hi = mid-1;
else
lo = hi = mid;
}
return children[me][lo];
}
int main( void ) {
scanf("%d%d", &n, &m);
for(int i = 0; i < m; ++i) {
int u, v;
scanf("%d%d", &u, &v);
--u; --v;
graph.insert_edge(edge( u, v));
graph.insert_edge(edge( v, u));
}
graph.init();
discover = finish = lowlink = depth = vector<int>(n, -1);
children.resize(n);
dfs(0, -1, 0);
int t;
scanf("%d%d", &m, &t);
for (int i = 0; i < m; ++i) {
int a, b, c, d;
scanf("%d%d%d", &a, &b, &c);
--a; --b; --c;
if (t == 1) {
scanf("%d", &d); --d;
if (is_descendant(c, d))
swap(c, d);
if (depth[d] != depth[c]+1)
printf("ja\n" );
else if (lowlink[d] < discover[d])
printf("ja\n" );
else if (is_descendant(a, d) == is_descendant(b, d))
printf("ja\n" );
else
printf("nej\n");
} else {
if (!is_descendant(a, c) && !is_descendant(b, c))
printf("ja\n");
else if (is_descendant(a, c) && is_descendant(b, c)) {
int e = find_related_child(c, a);
int f = find_related_child(c, b);
if (e == f)
printf("ja\n");
else if (lowlink[e] < discover[c] && lowlink[f] < discover[c])
printf("ja\n");
else
printf("nej\n");
} else {
if (is_descendant(a, c))
swap(a, b);
int e = find_related_child(c, b);
if (lowlink[e] < discover[c])
printf("ja\n");
else
printf("nej\n");
}
}
}
return 0;
}