ARC107F Sum of Abs

一个图，你要删去若干个点。删点的代价为\(A_i\)，最终得到的图的价值为所有连通块的\(B_i\)之和的绝对值。

最大化\(价值-代价\)。

\(n,m\le 300\)

可以转化成：你要给若干个点赋上\(+1,-1,delete\)，使得有边相连的不能一个为\(+1\)一个为\(-1\)。

不考虑限制先得到假的最优解，然后对于以上三种情况分别求出它们的代价。

最小割。将每个点\(i\)拆成\(X_i\)和\(Y_i\)。如果\(X_i,Y_i\in S\)，则表示\(+1\)；如果\(X_i,Y_i\in T\)，则表示\(-1\)；如果\(X_i\in S,Y_i \in T\)，则表示\(delete\)。为了避免\(Y_i\in S,X_i \in T\)的情况，一开始连边\((Y_i,X_i,\infty)\)。

如果有边\((u,v)\)，连\((Y_u,X_v,\infty),(Y_v,X_u,\infty)\)。

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 310
#define INF 1000000000
int n,m;
int a[N],b[N];
struct EDGE{
	int to,c;
	EDGE *las;
} e[N*10];
int ne;
EDGE *last[N*2];
int S,T;
void link(int u,int v,int c){
	e[ne]={v,c,last[u]};
	last[u]=e+ne++;
}
#define rev(ei) (e+(int((ei)-e)^1))
EDGE *cur[N*2];
int dis[N*2],gap[N*2],BZ;
int dfs(int x,int s){
	if (x==T)
		return s;
	int have=0;
	for (EDGE *&ei=cur[x];ei;ei=ei->las){
		if (ei->c && dis[x]==dis[ei->to]+1){
			int t=dfs(ei->to,min(ei->c,s-have));
			ei->c-=t,rev(ei)->c+=t,have+=t;
			if (have==s)	
				return s;
		}
	}
	cur[x]=last[x];
	if (!--gap[dis[x]])
		BZ=0;
	dis[x]++;
	gap[dis[x]]++;
	return have;
}
int flow(){
	gap[0]=T;
	BZ=1;
	int res=0;
	while (BZ)
		res+=dfs(S,INF);
	return res;
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i) scanf("%d",&a[i]);
	for (int i=1;i<=n;++i) scanf("%d",&b[i]);
	S=n+n+1,T=n+n+2;
	int sum=0;
	for (int i=1;i<=n;++i)
		if (b[i]>0){
			link(S,i,2*b[i]),link(i,S,0);
			link(i,i+n,b[i]+a[i]),link(i+n,i,INF);
			sum+=b[i];
//			printf("%d %d %d\n",S,i,2*b[i]);
//			printf("%d %d %d\n",i,i+n,b[i]+a[i]);
		}
		else{
			link(i+n,T,-2*b[i]),link(T,i+n,0);
			link(i,i+n,-b[i]+a[i]),link(i+n,i,INF);
			sum+=-b[i];
//			printf("%d %d %d\n",i+n,T,-2*b[i]);
//			printf("%d %d %d\n",i,i+n,-b[i]+a[i]);
		}
	for (int i=1;i<=m;++i){
		int u,v;
		scanf("%d%d",&u,&v);
		link(u+n,v,INF),link(v,u+n,0);
		link(v+n,u,INF),link(u,v+n,0);
	}
	printf("%d\n",sum-flow());
	return 0;
}

ARC107F Sum of Abs

原文：https://www.cnblogs.com/jz-597/p/13908550.html