Mamy nieskierowany graf o n wierzchołkach i m krawędziach. Każda krawędź ma wagę 1 lub 2. Każdemu wierzchołkowi v należy przypisać liczbę rzeczywistą w[v], tak by suma przypisanych liczb na każdej danej krawędzi była równa wadze krawędzi oraz suma wartości bezwzględnych w[v] była minimalna.
Na początek warto rozważyć uproszczenie, w którym waga każdej krawędzi wynosi 1. Wtedy, jeśli jakiemuś wierzchołkowi przypiszemy $x$, to wszystkim jego sąsiadom musimy przypisać $1-x$. Analogiczne, jak mamy wierzchołek z liczbą $1-x$, to jego sąsiadom musimy przypisać $1-(1-x) = x$. Takie wymuszenia działają w obrębie jednej spójnej składowej, więc dla każdej z nich wykonujemy osobne obliczenie.
Możemy więc zacząć od dowolnego wierzchołka składowej, przypisać mu $x$ i przeszukiwać dalej składową DFS-em, przypisując wymuszone wartości. Ciekawie zaczyna się, gdy w grafie mamy cykl, czyli pewnemu wierzchołkowi chcemy przypisać liczbę jeszcze raz.
Jeśli wierzchołkowi z przypisanym $y$ chcemy jeszcze raz przypisać $y$, to nic się nie dzieje (to oznacza, że znaleźliśmy cykl długości parzystej). W przeciwnym wypadku chcemy przypisać $1-y$. Zatem, jeśli rozwiązanie ma istnieć, to $y = 1-y$, czyli $y=1/2$. W konsekwencji wszystkie wierzchołki w tej spójnej składowej muszą mieć przypisane $1/2$.
Mamy więc dwa przypadki: albo składowa zawiera cykl nieparzystej długości (i wtedy wszystkie wierzchołki mają $1/2$), albo jest dwudzielna i wierzchołki z jednego zbioru mają przypisane $x$, a z drugiego mają przypisane $1-x$. Jeśli pierwszy zbiór jest mniejszy niż drugi, to optymalnie jest przyjąć $x=0$, a w przeciwnym wypadku $x=1$ (to nam zminimalizuje sumę wartości bezwzględnych przypisanych liczb).
Zacznijmy znowu od pewnego wierzchołka, któremu przypiszemy $x$. Wtedy jego sąsiadom przypisujemy albo $1-x$, albo $2-x$ w zależności od wagi krawędzi, która ich łączy. Możemy rozpisać sobie drzewko, w którym w korzeniu mamy $x$, a każdy węzeł z wartością $y$ ma dwoje dzieci o wartościach $1-y$ i $2-y$. Okazuje się, że wszystkie możliwe przypadki wartości w drzewie to $ax + b$, gdzie $a = \pm 1$, a $b$ jest dowolne całkowite.
Możemy znowu robić DFS-a i w każdym wierzchołku trzymać parę $(a,b)$, która oznacza, że musimy w nim przypisać wartość $ax + b$. Idąc z $(a,b)$ krawędzią o wadze $w$, dostajemy parę $(-a, w-b)$.
Ciekawie się robi, jeśli wierzchołkowi z parą $(a_1,b_1)$ chcemy przypisać inną parę $(a_2,b_2)$.
Jeśli $a_1=a_2$, to mamy cykl długości parzystej. Jeśli $b_1 \neq b_2$, to rozwiązanie nie istnieje.
Jeśli $a_1 \neq a_2$, to mamy $a_1 x + b_1 = a_2 x + b_2$, więc wartość $x$ jest wyznaczona jednoznacznie: $x = (b_2 - b_1) / (a_1 - a_2) = (b_2 - b_1) / (2a_1)$. Jeśli podczas przeszukiwania grafu znajdziemy co najmniej dwa różne rozwiązania na $x$, to rozwiązanie nie istnieje.
Po przejściu DFS-em mamy znów dwa przypadki: dla grafu niedwudzielnego mamy $x$ wyznaczone i po prostu wypisujemy $ax+b$ dla wszystkich wierzchołków. Dla grafu dwudzielnego $x$ jest nadal nieznane i musimy je dobrać tak, by zminimalizować sumę $\lvert ax+b \rvert$.
Wkład wierzchołków z jednego zbioru to będzie $\lvert x+b\rvert$ (bo $a=1$), a z drugiego zbioru to będzie $\lvert x-b\rvert$ (bo $a=-1$). Możemy zatem to zadanie sprowadzić do minimalizacji sumy odległości elementów $b_i$ od elementu $x$ na prostej. Znany jest fakt, że za $x$ optymalnie jest wziąć medianę elementów $b_i$.
const int N = 110000; int n,m; vector<pii> adj[N]; pii vis[N]; bool has; int fix; int ans[N]; vector<int> verts; void dfs(int v, int a, int b) { vis[v] = make_pair(a, b); verts.push_back(v); for (auto e : adj[v]) { int u = e.first, c = e.second; int na = -a; int nb = c - b; if (vis[u].first == 0) { dfs(u, na, nb); } else if (na == vis[u].first) { if (nb != vis[u].second) { printf("NO\n"); exit(0); } } else { int f = vis[u].second - nb; f *= na; if (has && fix != f) { printf("NO\n"); exit(0); } has = true; fix = f; } } } int main() { scanf("%d%d",&n,&m); REP(i,m) { int a,b,c; scanf("%d%d%d",&a,&b,&c); --a; --b; adj[a].emplace_back(b, c); adj[b].emplace_back(a, c); } REP(i,n) if (vis[i].first == 0) { verts.clear(); has = false; dfs(i, 1, 0); if (!has) { vector<int> z; for (int v : verts) { z.push_back(vis[v].first * vis[v].second); } nth_element(z.begin(), z.begin() + z.size()/2, z.end()); fix = -z[z.size()/2] * 2; } for (int v : verts) { ans[v] = vis[v].first * fix + 2 * vis[v].second; } } printf("YES\n"); REP(i,n) { printf("%.1lf ", ans[i] / 2.0); } printf("\n"); }
Program działa w czasie liniowym plus czas na znajdowanie mediany.