[图论记录]ARC107F Sum of Abs
command_block
2021-10-26 15:14:06
**题意** : 给一个无向图，点 $i$ 有 $a_i,b_i$ 两个权值。
可以花费 $a_i$ 的代价删掉 $i$ ，最终剩下来的各个连通块的 $\big|\sum b_i\big|$ 的和就是收益。
求 收益-代价 的最大值。
$n,m\leq 300$ ，时限$\texttt{2s}$。
------------
不太会从头推，直接给做法吧。
注意到绝对值可以看做正负抵消，具体地，记 $S^+=\sum_{i=1}^n[b_i>0]b_i,\ S^-=\sum_{i=1}^n[b_i<0]-b_i$ ，则有 $\big|\sum b_i\big|=\max(S^+,S^-)-\min(S^+,S^-)=S^++S^--2\min(S^+,S^-)$。
于是问题转化为最小化 $a+2\min(S^+,S^-)$ 的值。
考虑最小割，对于原图的边 $(u,v)$ ，连边 $u'\rightarrow v,\ v'\rightarrow u:+\infty$ 。 其中 $u'$ 是 $u$ 的“出点”。
对于点 $u$ ，若 $b_u<0$ 则连边 $u\rightarrow T: -2b_u$ ，否则连边 $S\rightarrow u: 2b_u$ 。
这样，对于一个联通块，要么全割正的 $b$ ，要么全割负的 $b$ ，最小割即为 $2\min(S^+,S^-)$ 。
接下来考虑 $a$ ，连边 $u\rightarrow u':a_u+|b_u|$ ，若将这条边割去，对连通性的影响等价于将 $u$ 点删去。这里要 $+b_u$ 因为删点会影响 $S^++S^-$ 。
跑个 Dinic 算最小割就好。
```cpp
#include<algorithm>
#include<cstdio>
#include<queue>
#define MaxN 605
#define MaxM 3050
using namespace std;
const int INF=1000000000;
int S,T;
struct Line{int nxt,t,cap;}l[MaxM];
int tl=1,fir[MaxN],dis[MaxN],cur[MaxN];
void adl(int f,int t,int cap){
l[++tl]=(Line){fir[f],t,cap};fir[f]=tl;
l[++tl]=(Line){fir[t],f,0};fir[t]=tl;
}
bool bfs()
{
static queue<int> q;
for (int i=1;i<=T;i++)
{cur[i]=fir[i];dis[i]=0;}
q.push(S);dis[S]=1;
while(!q.empty()){
int u=q.front();q.pop();
for (int i=fir[u];i;i=l[i].nxt)
if (l[i].cap&&!dis[l[i].t]){
dis[l[i].t]=dis[u]+1;
q.push(l[i].t);
}
}return dis[T];
}
int dfs(int u,int flow)
{
if (u==T)return flow;
int sum=0;
for (int &i=cur[u];i;i=l[i].nxt)
if (l[i].cap&&dis[l[i].t]==dis[u]+1){
int sav=dfs(l[i].t,min(flow,l[i].cap));
if (sav){
l[i].cap-=sav;l[i^1].cap+=sav;
sum+=sav;flow-=sav;
if (!flow)break;
}else dis[l[i].t]=-1;
}
return sum;
}
int n,m,a[MaxN];
int main()
{
scanf("%d%d",&n,&m);
int ans=0;S=n+n+1;T=S+1;
for (int u=1;u<=n;u++)scanf("%d",&a[u]);
for (int u=1,b;u<=n;u++){
scanf("%d",&b);
adl(u,u+n,a[u]+abs(b));ans+=abs(b);
if (b>0)adl(S,u,2*b);
if (b<0)adl(u+n,T,-2*b);
}
for (int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
adl(u+n,v,INF);
adl(v+n,u,INF);
}
while(bfs())ans-=dfs(S,INF);
printf("%d",ans);
return 0;
}
```