arc107F Sum of Abs

arc107F Sum of Abs

• 给一个无向图，点$i$有$a_i,b_i$两个权值。

• 现在你可以花费$a_i$的代价删掉$i$，最后剩下来的连通块的$|\sum b_i|$的和就是贡献。

• 求最大的：贡献-花费。

• $n,m\le 300$

Solution

• 考虑在同一个连通块内的$b_i>0,b_j<0$，它们之间互相抵消构成绝对值的一个过程，不难想到网络流（并且$n$这么小，一看就很适合流）
• $i,j$有连边的话，将$S$连向$i$，$j$连向$T$，那么跑最大流用$b_i+b_j-2maxflow$就相当于是相互抵消了。
• 很容易扩展一下，将原图中的边换成网络流上的边，那么如果有一个$b_i>0$和$b_j<0$连通，就一定会有流量的贡献，直到流满（也可以理解为最小割）。
• 再考虑$a_i$的影响，实际上就是拆点，把一个点$pr{e}_i,ne{x}_i$之间连一个$a_i+b_i$的边，割掉这条边相当于删掉这个点，同时也可以满足上面的连通性。

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define maxn 1005
#define maxm 500005
#define inf 2e9
using namespace std;

int n,m,i,j,k,S,T,ans;
int em,e[maxm],nx[maxm],ls[maxn],ec[maxm],cur[maxn];

void insert(int x,int y,int z){
	em++; e[em]=y; nx[em]=ls[x]; ls[x]=em; ec[em]=z;
	em++; e[em]=x; nx[em]=ls[y]; ls[y]=em; ec[em]=0;
}

int d[maxn],dis[maxn];
int bfs(){
	int t=0,w=1; memset(dis,0,sizeof(int)*(T+1));
	d[w]=S,dis[S]=1;
	while (t<w){
		int x=d[++t]; cur[x]=ls[x];
		for(int i=ls[x];i;i=nx[i]) if (ec[i]&&!dis[e[i]])
			d[++w]=e[i],dis[e[i]]=dis[x]+1;
	}
	return dis[T];
}

int dfs(int x,int p){
	if (x==T) return p;
	int res=p;
	for(int &i=cur[x];i;i=nx[i]) if (ec[i]&&dis[x]+1==dis[e[i]]){
		int tmp=dfs(e[i],min(res,ec[i]));
		ec[i]-=tmp,ec[i^1]+=tmp,res-=tmp;
		if (!res) break;
	}
	return p-res;
}

int maxflow(){
	int sum=0;
	while (bfs())
		sum+=dfs(S,inf);
	return sum;
}

int main(){
	freopen("ceshi.in","r",stdin);
	scanf("%d%d",&n,&m),em=1,S=2*n+1,T=2*n+2;
	for(i=1;i<=n;i++) scanf("%d",&k),insert(i,i+n,k);
	for(i=1;i<=n;i++) {
		scanf("%d",&k),ans+=abs(k);
		if (k<0) insert(i+n,T,-k*2);
		else insert(S,i,k*2);
		insert(i,i+n,abs(k));
	}
	for(i=1;i<=m;i++){
		scanf("%d%d",&j,&k);
		insert(j+n,k,inf),insert(k+n,j,inf);
	}
	printf("%d\n",ans-maxflow());
}