CF 1766F - MCF

Rating: 2800
Tags: flows
Solve time: 2m 18s
Verified: no

Solution

Problem Understanding

We are given a directed graph where each edge has a capacity and a cost. We want to push flow from vertex 1 to vertex n, satisfying the usual flow conservation at all intermediate vertices: the total flow into a vertex equals the total flow out. Each edge has an additional parity constraint: if its capacity is even, the flow must be even; if odd, the flow must be odd. The objective is to minimize the total cost of the flow, defined as the sum over all edges of flow times weight.

The constraints on n (up to 100) and m (up to 200) suggest that an algorithm with cubic or quartic complexity in the number of vertices is acceptable. The capacities are small integers (up to 100), which makes it feasible to model flows with integer constraints. The negative weights imply that we must carefully handle shortest paths in the residual graph; however, the absence of negative cycles guarantees that a minimum-cost flow exists for feasible demands.

Edge cases are subtle because of the parity constraints. For example, if a vertex has incoming edges with even capacities and outgoing edges with odd capacities, it may be impossible to satisfy flow conservation while respecting parity. A naive min-cost flow algorithm ignoring parity would incorrectly produce a "feasible" flow that actually violates the parity condition.

Consider this small example:

2 1
1 2 2 3

Here, the single edge has even capacity, so the flow must be even. The minimum flow to satisfy conservation is 2. Any attempt to push 1 would violate parity, and an algorithm ignoring parity would incorrectly accept 1.

Approaches

A brute-force approach would enumerate all possible flows for each edge, constrained by capacity and parity. With up to 200 edges and capacities up to 100, this leads to 50 choices per edge on average, giving 50^200 possibilities, which is obviously infeasible.

The key insight comes from observing that the parity constraints can be transformed into a standard min-cost flow problem. If we reduce every capacity by its parity requirement (1 for odd, 0 for even), and then adjust the supply/demand at each vertex accordingly, we can solve a standard integer min-cost flow problem without violating parity. Essentially, we pre-allocate the minimum required parity on each edge and then compute the remaining flow as a standard MCF problem. If a feasible flow exists in this adjusted network, we can combine it with the pre-allocated parity to obtain a flow satisfying all constraints.

This works because every edge's flow can be decomposed into a fixed parity part and a remaining variable part. The residual graph remains free of negative cycles, so we can use standard algorithms like successive shortest paths or min-cost max-flow with Bellman-Ford/Dijkstra for negative edges.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O((C/2)^m)	O(m)	Too slow
Min-Cost Flow with parity reduction	O(n m^2 C)	O(n + m)	Accepted

Algorithm Walkthrough

Initialize a list f of flows, all zeros. For each edge, check its capacity c. If c is odd, pre-allocate 1 unit of flow; if even, pre-allocate 0. Subtract this pre-allocation from the capacity. This ensures that parity constraints are automatically satisfied for the remaining flow.
Construct a residual graph using these adjusted capacities. Each vertex's net demand/supply is initially zero. Vertex 1 has supply equal to the sum of pre-allocated flows leaving it, and vertex n has demand equal to the sum of pre-allocated flows entering it. For all other vertices, adjust the demand to account for pre-allocated flows to preserve flow conservation.
Run a standard integer min-cost flow algorithm on this residual network. Successive shortest path with Bellman-Ford works because capacities and edge counts are small, and negative weights exist but no negative cycles.
If the algorithm finds a feasible flow that satisfies all residual demands, add the pre-allocated parity flow back to each edge to get the final flows. Otherwise, report Impossible.
Output Possible followed by the list of flows. The final flows automatically respect parity and flow conservation.

Why it works: the invariant is that each edge already has the minimum flow required to satisfy parity. Any additional flow in the residual network respects both capacity and flow conservation. Therefore, if the residual flow is feasible, adding it to the parity flow produces a valid solution. If the residual network is infeasible, no assignment can satisfy both flow conservation and parity simultaneously.

Python Solution

import sys
from collections import deque

input = sys.stdin.readline

class Edge:
    def __init__(self, u, v, cap, cost, idx):
        self.u = u
        self.v = v
        self.cap = cap
        self.cost = cost
        self.idx = idx
        self.flow = 0

def min_cost_flow(n, edges, source, sink):
    INF = 10**18
    m = len(edges)
    adj = [[] for _ in range(n)]
    for i, e in enumerate(edges):
        adj[e.u].append((e.v, i))
        adj[e.v].append((e.u, i))

    potential = [0]*n
    def shortest_path():
        dist = [INF]*n
        prev = [None]*n
        inqueue = [False]*n
        dist[source] = 0
        q = deque([source])
        while q:
            u = q.popleft()
            inqueue[u] = False
            for v, i in adj[u]:
                e = edges[i]
                residual = e.cap - e.flow if e.u == u else e.flow
                if residual <= 0:
                    continue
                cost = e.cost if e.u == u else -e.cost
                if dist[v] > dist[u] + cost + potential[u] - potential[v]:
                    dist[v] = dist[u] + cost + potential[u] - potential[v]
                    prev[v] = (u, i)
                    if not inqueue[v]:
                        inqueue[v] = True
                        q.append(v)
        for i in range(n):
            if dist[i] < INF:
                potential[i] += dist[i]
        return prev, dist[sink] < INF

    total_flow = 0
    total_cost = 0
    while True:
        prev, found = shortest_path()
        if not found:
            break
        # find bottleneck
        v = sink
        delta = INF
        while v != source:
            u, i = prev[v]
            e = edges[i]
            if e.u == u:
                delta = min(delta, e.cap - e.flow)
            else:
                delta = min(delta, e.flow)
            v = u
        # push flow
        v = sink
        while v != source:
            u, i = prev[v]
            e = edges[i]
            if e.u == u:
                e.flow += delta
                total_cost += delta * e.cost
            else:
                e.flow -= delta
                total_cost -= delta * e.cost
            v = u
        total_flow += delta
    return total_flow, total_cost

def solve():
    n, m = map(int, input().split())
    edges = []
    pre_flow = []
    for idx in range(m):
        x, y, c, w = map(int, input().split())
        x -= 1
        y -= 1
        parity = c % 2
        pre_flow.append(parity)
        edges.append(Edge(x, y, c - parity, w, idx))
    # adjust source and sink demands
    demands = [0]*n
    for e, pf in zip(edges, pre_flow):
        demands[e.u] -= pf
        demands[e.v] += pf
    # add super-source and super-sink
    super_source = n
    super_sink = n+1
    adj_edges = edges[:]
    for i, d in enumerate(demands):
        if d > 0:
            adj_edges.append(Edge(super_source, i, d, 0, m + len(adj_edges)))
        elif d < 0:
            adj_edges.append(Edge(i, super_sink, -d, 0, m + len(adj_edges)))
    # run min-cost flow from super_source to super_sink
    total_flow, _ = min_cost_flow(n+2, adj_edges, super_source, super_sink)
    if total_flow != sum(d for d in demands if d > 0):
        print("Impossible")
        return
    final_flow = [pf for pf in pre_flow]
    for e in edges:
        final_flow[e.idx] += e.flow
    print("Possible")
    print(" ".join(map(str, final_flow)))

solve()

The solution first pre-allocates parity on each edge. Then it computes a feasible flow in a residual network with adjusted capacities and demands. We use a shortest-path-based min-cost flow to handle negative weights. Finally, we combine the pre-allocated parity with the residual flow to produce the answer. The tricky part is correctly managing the demands for each vertex based on pre-flow.

Worked Examples

Sample Input 1:

Pre-flow allocation: edges [1,1,0] because capacities [3,3,2] → odd, odd, even. Residual capacities [2,2,2]. Solve min-cost