「ARC107F」Sum of Abs

发表于 分类于

$Link$

给定一个 $n$ 个点 $m$ 条边的简单无向图，每个点有 $a_i,b_i$ 两个权值。

定义一个联通块的价值为联通块中所有点的 $b_i$ 之和的绝对值，一个图的价值为这张图的所有极大联通块的价值和。

你可以以 $a_i$ 的代价删去第 $i$ 个点以及所有与它相连的边。

最大化图的价值 $-$ 代价。

$1\le n\le300,1\le m\le300,1\le a_i\le10^6,|b_i|\le10^6$。

考虑把这个绝对值拆开，变成两个值取 $\operatorname{max}$。

那每个点的贡献就是 $b_i$ 或者 $-b_i$，并且有边相连的点应该同取 $b_i$ 或者同取 $-b_i$。

先把答案加上 $\sum_{i=1}^{n}|b_i|$，再考虑割掉最小割使其合法。

接下来是妙妙建图。

拆点之后 $S\to i_1\to i_2\to T$，分别表示取 $b_i$，删掉，取 $-b_i$。

边权分两种情况，$b_i\ge0$ 为 $0,a_i+b_i,2b_i$，$b_i<0$ 为 $-2b_i,a_i-b_i,0$，分析一下容易得到。

对于有边相邻的点的限制，对于边 $(u,v)$，连 $v_2\to u_1$ 和 $u_2\to v_1$，边权为 $+\infty$ 的边。

这样就满足了边的限制，并且如果一个点被删掉了，限制也会消失。

直接跑最大流即可。

$code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
inline int read()
{
    int f = 1, x = 0;
    char ch;

    do{
        ch = getchar();
        if (ch == '-')
            f = -1;
    }while(ch < '0' || ch > '9');
    do{
        x = x * 10 + ch - '0';
        ch = getchar();
    }while(ch >= '0' && ch <= '9');
    return f * x;
}
const int N = 1e3;
const int M = 2e3;
const int SIZE = (N + 1) * 4;

int n, m;
int a[N + 1], b[N + 1];
int ans;
namespace Dinic
{
struct Edge {
    int	to, next, oppo;
    int	done, maxx;
} edge[(M << 1) + 1];
int s = 0, t = N;
int tot, start[N + 1], cur[N + 1];
queue<int> q;
int vis[N + 1], dep[N + 1];
inline void addedge(int u, int v, int flow)
{
    edge[++tot] = Edge{ v, start[u], tot + 1, 0, flow };
    start[u] = tot;
    edge[++tot] = Edge{ u, start[v], tot - 1, 0, 0 };
    start[v] = tot;
    return;
}
inline bool bfs()
{
    memset(dep, 0, SIZE);
    memset(vis, 0, SIZE);
    q.push(s);
    dep[s] = vis[s] = 1;
    while (q.size()) {
        int u = q.front();
        q.pop();
        for (int i = start[u]; i; i = edge[i].next) {
            int v = edge[i].to;
            if (!vis[v] && edge[i].done < edge[i].maxx) {
                dep[v] = dep[u] + 1;
                vis[v] = 1;
                q.push(v);
            }
        }
    }
    return dep[t];
}
inline int dfs(int u, int flow)
{
    if (u == t || !flow)
        return flow;
    int val = 0;

    for (int &i = cur[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if (dep[v] == dep[u] + 1) {
            int w = dfs(v, min(flow, edge[i].maxx - edge[i].done));
            if (w > 0) {
                edge[i].done += w;
                edge[edge[i].oppo].done -= w;
                val += w;
                flow -= w;
                if (!flow)
                    break;
            }
        }
    }
    return val;
}
inline void dinic()
{
    while (bfs()) {
        memcpy(cur, start, SIZE);
        ans -= dfs(s, 2147483647);
    }
    return;
}
}

int main()
{
    n = read();
    m = read();
    for (int i = 1; i <= n; i++)
        a[i] = read();
    for (int i = 1; i <= n; i++) {
        b[i] = read();
        if (b[i] > 0) {
            ans += b[i];
            Dinic::addedge(Dinic::s, i * 2 - 1, 0);
            Dinic::addedge(i * 2 - 1, i * 2, a[i] + b[i]);
            Dinic::addedge(i * 2, Dinic::t, 2 * b[i]);
        } else {
            ans -= b[i];
            Dinic::addedge(Dinic::s, i * 2 - 1, -2 * b[i]);
            Dinic::addedge(i * 2 - 1, i * 2, a[i] - b[i]);
            Dinic::addedge(i * 2, Dinic::t, 0);
        }
    }
    for (int i = 1; i <= m; i++) {
        int x = read(), y = read();
        Dinic::addedge(x * 2, y * 2 - 1, 1e9);
        Dinic::addedge(y * 2, x * 2 - 1, 1e9);
    }

    Dinic::dinic();

    printf("%d\n", ans);
    return 0;
}