「JSOI2013」旅行时的困惑

「JSOI2013」旅行时的困惑

传送门

由于我们的图不仅是一个 \(\text{DAG}\) 而且在形态上还是一棵树，也就是说我们为了实现节点之间互相可达，就必须把每条边都覆盖一次，因为两个点之间的路径是唯一的。

那么题意就变成了：每次在图上选出一条路径，覆盖上面的边，求最小的路径数使得所有边都被覆盖至少一次。

看到这里我不禁联想起这道题

那么对于这道题我们就让源点 \(S\) 向所有点连上界为 \(+\infty\) ，下界为 \(0\) 的边，所有点向汇点 \(T\) 连边同理，然后原图中的边连成上界为 \(+\infty\) ，下界为 \(1\) 的边，然后跑一个有源汇上下界最小流即可。

由于这题数据范围还是相对有点大的，所以建议把能加的优化都加上。

#include <cstring>

#include <cstdio>

#define rg register

#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

template < class T > inline T min(T a, T b) { return a < b ? a : b; }

template < class T > inline void read(T& s) {

    s = 0; int f = 0; char c = getchar();

    while ('0' > c || c > '9') f |= c == '-', c = getchar();

    while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();

    s = f ? -s : s;

}

const int _ = 2e5 + 10, __ = 1e6 + 10, INF = 2147483647;

int tot = 1, head[_]; struct Edge { int v, w, nxt; } edge[__ << 1];

inline void Add_edge(int u, int v, int w) { edge[++tot] = (Edge) { v, w, head[u] }, head[u] = tot; }

inline void link(int u, int v, int w) { Add_edge(u, v, w), Add_edge(v, u, 0); }

int n, s, t, S, T, d[_], dep[_], cur[_];

inline void Link(int u, int v, int l, int r) { link(u, v, r - l), d[u] -= l, d[v] += l; }

inline int bfs() {

    static int hd, tl, Q[_];

    memset(dep + 1, 0, sizeof (int) * (n + 4));

    hd = tl = 0, dep[Q[++tl] = S] = 1;

    while (hd < tl) {

	    int u = Q[++hd];

	    for (rg int i = head[u]; i; i = edge[i].nxt) {

	        int v = edge[i].v, w = edge[i].w;

	        if (dep[v] == 0 && w)

		        dep[v] = dep[u] + 1, Q[++tl] = v;

    	}

    }

    return dep[T] > 0;

}

inline int dfs(int u, int flow) {

    if (u == T) return flow;

    for (rg int& i = cur[u]; i; i = edge[i].nxt) {

	    int v = edge[i].v, w = edge[i].w;

	    if (dep[v] == dep[u] + 1 && w) {

	        int res = dfs(v, min(flow, w));

	        if (res) { edge[i].w -= res, edge[i ^ 1].w += res; return res; }

	    }

    }

    return 0;

}

inline int Dinic() {

    int res = 0;

    while (bfs()) {

	    for (rg int i = 1; i <= n + 4; ++i) cur[i] = head[i];

	    while (int d = dfs(S, INF)) res += d;

    }

    return res;

}

int main() {

#ifndef ONLINE_JUDGE

    file("cpp");

#endif

    read(n), s = n + 1, t = n + 2, S = n + 3, T = n + 4;

    for (rg int u, v, i = 1; i < n; ++i) read(u), ++u, read(v), ++v, Link(u, v, 1, INF);

    for (rg int i = 1; i <= n; ++i) Link(s, i, 0, INF), Link(i, t, 0, INF);

    for (rg int i = 1; i <= n; ++i) {

	    if (d[i] > 0) link(S, i, d[i]);

	    if (d[i] < 0) link(i, T, -d[i]);

    }

    Dinic();

    link(t, s, INF);

    Dinic();

    printf("%d\n", edge[tot].w);

    return 0;

}