ARC107F Sum of Abs
Problem
\(N\) 个点 \(M\) 条边的无向图，每个点有两个权值 \(A_i\) 和 \(B_i\)。可以用 \(A_i\) 的代价删除第 \(i\) 个节点。并删除与这个点相连的边。一个极大连通块的权值定义为 \(B_i\) 的权值和的绝对值。
删除一些节点后，收益定义为所有极大连通块权值之和减去代价和。求最大的可能收益。
Solution
先强制将所有点删去，产生 \(-\sum_{i=1}^{n}A_i\) 的收益。然后考虑怎么加点。
最终的极大连通块可以分为取绝对值前权值为负的和权值为正的。所以加入一个点可能产生两种贡献，\(A_i+B_i\) 和 \(A_i-B_i\)
考虑极大连通块的限制，一条边连接的两个点不可能同时产生两种不同的贡献。
这里可以想到拆点，将一个点拆成正点和负点（正负仅用于区分，相当于编号）。
- 对于每个点 \(u\)：\(w_{u^+}=A_i+B_i\)，\(w_{u^-}=A_i-B_i\) 连 \(u^+-u^-\)。
- 对于每条边 \(u-v\)：连 \(u^+-v^-\)，\(u^--v^+\)。
这样就问题转化为了求新建出图的最大全独立集。
AC Code
#include <bits/stdc++.h>
namespace _default{
using namespace std;
#define lovely return
#define _lzy_ 0
#define LL long long
#define int long long
#define DB double
#define PII std::pair<int, int>
#define X first
#define Y second
#define uF(i, x, y) for(int i = (x); i <= (y); ++ i)
#define uf(i, x, y) for(int i = (x); i < (y); ++ i)
#define dF(i, x, y) for(int i = (x); i >= (y); -- i)
#define df(i, x, y) for(int i = (x); i > (y); -- i)
#define ef(i, u) for(int i = head[(u)]; i; i = ne[i])
#define sett(x, y) memset(x, y, sizeof x)
#define copy(x, y) memcpy(x, y, sizeof x)
const int MOD = 1e9 + 7, INF = 0x3f3f3f3f;
const DB EPS = 1e-8;
template<typename T> T read(){
T s = 0; int f = 0; char ch = getchar();
while(!isdigit(ch)){if(ch == '-') f = 1; ch = getchar();}
while(isdigit(ch)) s = s * 10 + ch - 48, ch = getchar();
return f ? ~s + 1 : s;
}
template<typename T> void write(T x, const char *s = ""){
static int st[40]; int top = 0;
if(x < 0){putchar('-'); x = -x;}
if(!x) putchar('0');
while(x) st[++ top] = x % 10, x /= 10;
while(top) putchar(st[top --] + 48);
printf("%s", s);
}
template<typename T> void updmin(T &x, T y){if(x > y) x = y;}
template<typename T> void updmax(T &x, T y){if(x < y) x = y;}
template<typename T> void updadd(T &x, T y){(x += y % MOD) %= MOD;}
template<typename T> void updmul(T &x, T y){(x *= y % MOD) %= MOD;}
int cmp(DB a, DB b){if(fabs(a - b) < EPS) return 0; return a - b > EPS ? 1 : -1;}
}
using namespace _default;
int n, m, s, t, sum;
int a[305], b[305];
PII oe[305];
int head[605], ne[3005], to[3005], idx = 1;
int flw[3005];
int hgt[605], cur[605];
void Add_Edge(int u, int v, int w){
to[++ idx] = v, ne[idx] = head[u], head[u] = idx;
flw[idx] = w;
}
bool BFS(){
sett(hgt, -1); hgt[s] = 0;
queue<int> q; q.push(s);
while(!q.empty()){
int u = q.front(); q.pop();
cur[u] = head[u];
ef(i, u){
int v = to[i];
if(hgt[v] != -1 || !flw[i]) continue;
hgt[v] = hgt[u] + 1;
q.push(v);
}
}
return hgt[t] != -1;
}
int DFS(int u, int ori){
if(u == t) return ori;
int rest = ori;
for(int i = cur[u]; i; i = ne[i]){
int v = to[cur[u] = i];
if(!flw[i] || hgt[v] != hgt[u] + 1) continue;
int delta = DFS(v, min(rest, flw[i]));
flw[i] -= delta, flw[i ^ 1] += delta, rest -= delta;
if(!rest) break;
}
return ori - rest;
}
int Dinic(){
int res = 0;
while(BFS()) res += DFS(s, INF);
return res;
}
signed main(){
n = read<int>(), m = read<int>();
uF(i, 1, n) sum += (a[i] = read<int>());
uF(i, 1, n) b[i] = read<int>();
uF(i, 1, m) oe[i].X = read<int>(), oe[i].Y = read<int>();
s = n + n + 1, t = n + n + 2;
uF(i, 1, n){
Add_Edge(i, i + n, INF), Add_Edge(i + n, i, 0);
if(a[i] + b[i] > 0) Add_Edge(s, i, a[i] + b[i]), Add_Edge(i, s, 0);
else sum -= a[i] + b[i];
if(a[i] - b[i] > 0) Add_Edge(i + n, t, a[i] - b[i]), Add_Edge(t, i + n, 0);
else sum -= a[i] - b[i];
}
uF(i, 1, m)
Add_Edge(oe[i].X, oe[i].Y + n, INF), Add_Edge(oe[i].Y + n, oe[i].X, 0),
Add_Edge(oe[i].Y, oe[i].X + n, INF), Add_Edge(oe[i].X + n, oe[i].Y, 0);
write(sum - Dinic(), "\n");
lovely _lzy_;
}