CF1610F 题解

GaryH · 2021-11-28 10:31:58 · 题解

CF1610F 题解

题意： 给一张无向图，边权为1或2，要求给每一条边定向，

使得 \sum _ {u} [|\sum _i i \times d_i(u)| = 1] 最大，

其中 d_i(u) 为定向后点 u 的权为 i 的边的入度和减出度和。

在这里提供两种做法。

法一：

定义 g_i(u) 代表定向前原图中与 u 相连的权为 i 的边的数量。

首先发现，若存在某个点 u，使得 g_1(u) 为偶数，则 |\sum _ i i \times d_i(u)| 必不可能为1，

故最终答案的上界是 sum _u [g_1(u) \mod 2 = 1]。我们猜想，这个上界一定可以达到。

我们再次仔细地观察一下，发现：

若有三个点 u, v, w，其中 (u, v) 与 (v, w) 间各有一条权为 x 的边。

那么，我们此时将这两条边删除，并在 (v, w) 间添上一条权为 x 的边，

这样并不会对答案造成影响，也就是说新图和原图在这个问题上等价，因为：

我们这样做并未对 g_x(u) 和 g_x(w) 造成影响，而也并没有改变 g_x(v) 的奇偶性，

故答案上界仍然不变。我们称这样的操作为缩边操作。

那我们就不停地进行缩边的操作，直到在图中无法进行任何缩边操作。

那么此时，我们发现，现在的图中每个点至多有两条边相连，且所有出边的权互不相同。

也就是说，现在的图由若干个环和链组成，其中每个环和链的边权都呈 1.2 交错的状态。

容易发现，任意两个环或链间互不影响，故可以对每条环和链分别考虑。

而对于每一个环或每一条链，我们只需要找出其上面的某一条边，并任意定一个向，

再沿着这条边的方向遍历整个环或链，并将每条边的方向定成其被遍历的方向即可。

具体来说，就是：

如果有一条边 (u,v)，在遍历这条边时，我们先遍历到点 u，再遍历的整条边，

我们就将该边方向定成 u \to v，否则就将该边方向定成 v \to u.

以上的定向方法必然最优，因为所有 d_1 值为奇数的点的 |\sum _i i \times d_i(u)| 都等于 1.

那么，我们发现，我们给最后这张新图定向后，答案已经等于上界了，

或者说，就是此时定的向使得： \sum _ {u} [|\sum _i i \times d_i(u)| = 1] \leq \sum _u [g_1(u) \mod 2 = 1] 取等。

也就是说，我们现在需要考虑的就是，如何从新图的定向方案推出原图的定向方案。

我们注意到，若有一条已定向的边 u\to v 由 (u,t) 和 (t,v) 两条边组成，那么：

在原图中，我们就可以将 (u,t) 的方向定成 u \to t，将(t, v) 的方向定成 t \to v.

我们发现，一次次的缩边操作，使边与边之间形成了一个形如二叉树森林的关系，

其中一条边的左右儿子边的含义，是该边由其左右儿子边进行的缩边操作形成。

那么我们只需要建出这个森林，就可以由新图中边的方向，推出原图中边的方向。

容易发现，这样的定向方法，使得原图的答案达到了上界，故这样做是足够优秀的。

至于时间复杂度，可以做到 O(m \log m)，可以通过。

法二：

和法一相同之处在于，这个方法的目标，也是让答案达到上界。

我们构造一张点数为 2n + 1 的图，具体如下：

定义 g_i(u) 代表定向前原图中与 u 相连的权为 i 的边的数量。

定义 w(u,v) 为原图中 u,v 两点间边的边权，若 (u,v) 间不存在边则 w(u,v) = -1.

对 \forall i,j \in [1,n] ，若 w(i,j) = 1，则在新图中有一条边 (i,j)；
对 \forall i,j \in [n+1,2n] ，若 w(i,j) = 2，则在新图中有一条边 (i,j)；
对 \forall i \in [1,n]，有：
1. 若 g_1(i),g_2(i) 皆为奇数，则在新图中有一条边 (i,i+n)；
2. 若只有 g_1(i) 为奇数，则在新图中有一条边 (i, 2n + 1)；
3. 若只有 g_2(i) 为奇数，则在新图中有一条边 (i + n, 2n + 1).

我们发现，这样的图中一定存在一条欧拉回路，因为所有点的度数都是偶数。

那我们在图中找出任意一条欧拉回路，并沿着遍历方向给每条边定向，

最后再将原图的边与新图中上方 1.2. 两种边一一对应后定向。

我们发现，这样定向使得每个 g_1(u) 为奇数的点 u 最后都对答案产生了 1 的贡献。

至于原因，请读者自行思考。

这样的复杂度是线性的，优于第一种做法，且很好写。

下面给出法二的代码：（如果想看法一代码，可以看CF官解）

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define SZ(x) (int(x.size()))
#define pii pair < int , int >
#define rep(i, a, b) for (int i = (a); i <= (b); i++)

const int N (6e5 + 10);
vector < pii > G[N];
int n, m, ans, flg[N], res[N];
void add (int u, int v, int i) {
    G[u].pb(mp(v, i)), G[v].pb(mp(u, i));
}
void dfs (int u) {
    while (!G[u].empty()) {
        pii e = G[u].back(); G[u].pop_back();
        if (res[e.se] < 0) res[e.se] = (u < e.fi), dfs(e.fi);
    }
}
int main () {
    n = read(), m = read();
    rep (i, 1, m) {
        int u = read(), v = read(), w = read(); flg[i] = (u < v);
        if (w == 1) add (u, v, i); else add (u + n, v + n, i);
    }
    rep (i, 1, n) ans += (SZ(G[i]) & 1);
    cout << ans << endl;
    rep (i, 1, n) {
        if ((SZ(G[i]) & 1) && (SZ(G[i + n]) & 1)) add (i, i + n, i + m);
        else {
            if (SZ(G[i]) & 1) add (i, n * 2 + 1, i + m);
            if (SZ(G[i + n]) & 1) add (i + n, n * 2 + 1, i + m);
        }
    }
    memset (res, -1, sizeof(res)), rep (i, 1, n * 2 + 1) dfs (i);
    rep (i, 1, m) putchar (2 - (flg[i] != res[i]) + '0');
    return 0;
}