AT_arc107_f Sum of Abs 题解

题目链接：[https://atcoder.jp/contests/arc107/tasks/arc107_f]([ARC107F] Sum of Abs)

初始状态设为全部点都不选，考虑每个点有三种状态：删掉，在一个正的联通块中，在一个负的联通块中，对应的权值分别为：$ 0, A_i+B_i, A_i-B_i $，然后我们可以拆点，每个点拆成正点和负点，权值分别为 $ A_i+B_i $ 和 $ A_i-B_i $，每个点的正点和负点相连，原图中之间有边的两个点的正负相反的点相连（点 A 的正点连点 B 的负点，点 B 的正点连点 A 的负点），然后跑一个最大权独立集即可。

• 为什么是对的

因为正点和负点对应的就是在一个正的联通块中和在一个负的联通块中这两种状态，同一个点的正点和负点连边使得不能同时取两个状态，原图中之间有边的两个点的正负相反的点相连保证相邻点如果两个都没被删那么取的符号一定相等。

代码：

#include<bits/stdc++.h>
#define int long long
#define debug() cout<<"come here\n"
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int,int>
#define pb push_back
using namespace std;
int qpow(int a,int b,int p){int ret=1;while(b){if(b&1)ret=(ret*a)%p;a=(a*a)%p;b>>=1;}return ret;}
inline int read(){int ret=0,f=1;char ch=getchar();while(ch<'0'||ch>'9')f=(ch=='-'?-1:f),ch=getchar();while(ch>='0'&&ch<='9')ret=(ret<<3)+(ret<<1)+(ch^48),ch=getchar();return ret*f;}
inline void write(int x){if(x<0){putchar('-');write(-x);return ;}if(x>9)write(x/10);putchar((char)(x%10+48));}
inline void writech(int x,char ch){write(x);putchar(ch);}
int n,m,S,T;
int to[1000001],val[1000001],nxt[1000001],head[10001],tot=-1,now[10001];
int dep[10001],sum;
void add(int u,int v,int w)
{if(w<=0){sum-=w;return ;}to[++tot]=v;val[tot]=w;nxt[tot]=head[u];head[u]=tot;to[++tot]=u;val[tot]=0;nxt[tot]=head[v];head[v]=tot;
}
bool bfs()
{memset(dep,0,sizeof(dep));dep[S]=1;queue<int> q;q.push(S);now[S]=head[S];while(q.size()){int u=q.front();q.pop();for(int i=head[u];~i;i=nxt[i]){int v=to[i];if(val[i]&&!dep[v]){dep[v]=dep[u]+1;now[v]=head[v];q.push(v);}}}return dep[T];
}
int dfs(int u,int flow)
{if(u==T)return flow;int nwfw=0;for(int i=now[u];~i&&flow;i=nxt[i]){now[u]=i;int v=to[i];if(val[i]&&dep[v]==dep[u]+1){int tmp=dfs(v,min(val[i],flow));val[i]-=tmp;val[i^1]+=tmp;flow-=tmp;nwfw+=tmp;}}if(nwfw==0)dep[u]=0;return nwfw;
}
int dinic()
{int ret=0;while(bfs())ret+=dfs(S,1000000000);return ret;
}
signed main()
{
//	ios::sync_with_stdio(0);
//	cin.tie(0);
//	cout.tie(0);memset(head,-1,sizeof(head));n=read(),m=read();sum=0;vector<int> a(n+1,0),b(n+1,0);for(int i=1;i<=n;i++){a[i]=read();sum+=a[i];}S=0;T=n+n+1;for(int i=1;i<=n;i++){b[i]=read();add(S,i,a[i]+b[i]);add(i,i+n,INF);add(i+n,T,a[i]-b[i]);}for(int i=1;i<=m;i++){int u=read(),v=read();add(u,v+n,INF);add(v,u+n,INF);}writech(sum-dinic(),'\n');return 0;
}