思路:
直接套用二元关系最小割,对于这道题而言非常朴素,而且不用考虑某些变量为负数还需要构造二分图的情况,很容易就水过去了.
现在我们仅考虑二元关系:(我们将所有收益预先加到一起,那么现在仅是需要减去最小的损失)
考虑两个点\(x,y\)以及一条边\(E(x,y)\):
\(x\in{A},y\in{A},cost=C_1=E_B\)
\(x\in{A},y\in{B},cost=C_2=E_A+E_B+E_C\)
\(x\in{B},y\in{A},cost=C_3=E_A+E_B+E_C\)
\(x\in{A},y\in{B},cost=C_4=E_A\)
连边\((S,x,a),(S,y,b),(x,T,c),(y,T,d),(x,y,e),(y,x,f)\).
随后不难发现:
\(C_1=c+d,C_2=b+c+e,C_3=a+d+f,C_4=a+b\)
好辣!如果我们能够直接解出\(a,b,c,d,e,f\)不是就非常好了么.
注意到如果\(a,b,c,d\)是负数我们并不用在意,因为\(a,c\)中只能选择一个,\(b,d\)中也只能选择一个,所以我们可以将边权均增大一个值,最终再减去即可.
可是\(e,f\)并不可以这样草率处理.
当\(C_2+C_3-C_1-C_2>0\)时,\(e,f\)可以取大于0的数,而\(a,b,c,d\)随意选择,问题可以解决.
如果不是的话,我们就需要在一对二元关系中,将其中一个点的意义反向,当然这有一个条件,二元关系必须不能存在奇环.不过这都是后话了.
这道题我们显然不用构造二分图,直接列出式子见图就行了.为了避免实数网络流将边权扩大二倍.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
static const int INF=0x3f3f3f3f;
struct MaxflowSolver{
static const int V=10010;
static const int E=600010;
int head[V],next[E],end[E],flow[E],ind;
int gap[V],stk[V],d[V],top,cur[V];
inline void reset(){ind=top=0,memset(head,-1,sizeof head);}
inline void addedge(int a,int b,int f){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;}
inline void make(int a,int b,int f){addedge(a,b,f),addedge(b,a,0);}
inline void bfs(int T){
static int q[V];int fr=0,ta=0;
memset(gap,0,sizeof gap),memset(d,-1,sizeof d),++gap[d[T]=0],q[ta++]=T;
while(fr^ta){
int i=q[fr++];for(int j=head[i];j!=-1;j=next[j])if(d[end[j]]==-1)++gap[d[end[j]]=d[i]+1],q[ta++]=end[j];
}
}
inline int Maxflow(int S,int T,int cnt){
int res=0,u=S,ins,Min,i;bfs(T),memcpy(cur,head,sizeof cur);
while(d[S]<cnt){
if(u==T){
for(Min=INF,i=0;i<top;++i)if(flow[stk[i]]<Min)Min=flow[stk[i]],ins=i;
for(res+=Min,i=0;i<top;++i)flow[stk[i]]-=Min,flow[stk[i]^1]+=Min;
u=end[stk[top=ins]^1];
}
if(u!=T&&!gap[d[u]-1])break;
bool find=0;
for(int&j=cur[u];j!=-1;j=next[j])if(flow[j]&&d[u]==d[end[j]]+1){find=1,ins=j;break;}
if(find)stk[top++]=cur[u]=ins,u=end[ins];
else{
Min=cnt;for(int j=head[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]<Min)Min=d[end[j]],cur[u]=j;
if(!--gap[d[u]])break;++gap[d[u]=Min+1];
if(u!=S)u=end[stk[--top]^1];
}
}return res;
}
}Stg;
int in[10010],out[10010];
int main(){
int n,m;scanf("%d%d",&n,&m);register int i,j;
Stg.reset();
int S=0,T=n+1;
in[1]=out[n]=INF;
int a,b,x,res=0;
for(i=2;i<n;++i)scanf("%d",&x),res+=x<<1,in[i]+=x<<1;
for(i=2;i<n;++i)scanf("%d",&x),res+=x<<1,out[i]+=x<<1;
int Ea,Eb,Ec;
while(m--){
scanf("%d%d%d%d%d",&a,&b,&Ea,&Eb,&Ec),res+=2*Ea+2*Eb;
in[a]+=Ea,in[b]+=Ea,out[a]+=Eb,out[b]+=Eb;
Stg.make(a,b,Ea+Eb+2*Ec),Stg.make(b,a,Ea+Eb+2*Ec);
}
for(i=1;i<=n;++i){
if(in[i])Stg.make(S,i,in[i]);
if(out[i])Stg.make(i,T,out[i]);
}
printf("%d",(res-Stg.Maxflow(S,T,n+2))>>1);
return 0;
}