Graf

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.

Wszystkie wagi równe

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).

Przypadek ogólny

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\ne b_2$, to rozwiązanie nie istnieje.

Jeśli $a_1\ne 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ę $|ax+b|$.

Wkład wierzchołków z jednego zbioru to będzie $|x+b|$ (bo $a=1$), a z drugiego zbioru to będzie $|x-b|$ (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.