Description：

给一个图， $1$ 属于 $A$ 集合， $2$ 属于 $B$ 集合，每个点在 $A$ 或 $B$ 有不同的价值 $VA,VB$ ，每条边如果两个点都在 $A$ 或 $B$ 有不同的加成 $EA,EB$ ，如果分别在不同集合有扣分 $EC$ 。

$1\le n \le 10000$

Solution：

同小 $M$ 的作物，每个点从原点向这个点连在 $VA$ ，向汇点连 $VB$ ，对于每条边 $(u,v)$ 新建两个点 $X,Y$ ，连边 $S\xrightarrow{EA} X$ , $X\xrightarrow {INF}u$ , $X\xrightarrow {INF}v$ , $u\xrightarrow {INF}Y$ , $v\xrightarrow {INF}Y$ , $Y\xrightarrow {INF}T$ , $u\xleftarrow {EC}v$ , $u\xrightarrow {EC}v$

然后跑最小割，用 $\begin{align}\sum VA+\sum VB+\sum EA+\sum EB-\end{align}$ 最小割就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int n,m;

#define MAXN 10010

#define MAXM 40010

int vala[MAXN],valb[MAXN];

#define INF 0x3f3f3f3f

int s,t;

struct edge

{

	int to,nxt,f;

}e[MAXN * 2 * 2 + MAXM * 8 * 2];

int edgenum = 0;

int lin[MAXN + MAXM * 2];

inline void add(int a,int b,int f)

{

	e[edgenum].to = b;e[edgenum].f = f;e[edgenum].nxt = lin[a];lin[a] = edgenum;++edgenum;

	e[edgenum].to = a;e[edgenum].f = 0;e[edgenum].nxt = lin[b];lin[b] = edgenum;++edgenum;

	return;

}

int ch[MAXN + MAXM * 2];

inline bool BFS()

{

	queue<int> q;q.push(s);

	memset(ch,-1,sizeof(ch));ch[s] = 0;

	while(!q.empty())

	{

		register int k = q.front();q.pop();

		for(register int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(ch[e[i].to] == -1 && e[i].f)

			{

				ch[e[i].to] = ch[k] + 1;

				q.push(e[i].to);

			}

		}

	}

	return (ch[t] != -1);

}

int flow(int k,int f)

{

	if(k == t)return f;

	register int r = 0;

	for(register int i = lin[k];i != -1 && f > r;i = e[i].nxt)

	{

		if(ch[e[i].to] == ch[k] + 1 && e[i].f)

		{

			register int l = flow(e[i].to,min(f - r,e[i].f));

			e[i].f -= l;r += l;e[i ^ 1].f += l;

		}

	}

	if(r == 0)ch[k] = -1;

	return r;

}

inline int dinic()

{

	register int ans = 0,r;

	while(BFS())while(r = flow(s,INF))ans += r;

	return ans;

}

int main()

{

	memset(lin,-1,sizeof(lin));

	n = read();m = read();

	for(register int i = 2;i <= n - 1;++i)vala[i] = read();vala[1] = INF;vala[n] = 0;

	for(register int i = 2;i <= n - 1;++i)valb[i] = read();valb[1] = 0;valb[n] = INF;

	s = n + 2 * m + 1;t = s + 1;

	register int ans = 0;

	for(register int i = 1;i <= n;++i)

	{

		add(s,i,vala[i]);

		add(i,t,valb[i]);

		if(i != 1 && i != n)ans += vala[i] + valb[i];

	}

	register int x,y,a,b,c;

	for(register int i = 1;i <= m;++i)

	{

		x = read();y = read();a = read();b = read();c = read();

		ans += a + b;

		add(s,n + i * 2 - 1,a);add(n + i * 2,t,b);

		add(n + i * 2 - 1,x,INF);add(n + i * 2 - 1,y,INF);

		add(x,n + i * 2,INF);add(y,n + i * 2,INF);

		add(x,y,c);add(y,x,c);

	}

	cout << ans - dinic() << endl;

	return 0;

}

Another Solution：

二元关系最小割模型。

首先列出方程：

如果 $x$ 和 $y$ 都在 $S$ ：价值为 $VA_x+VA_y+EA_{x,y}$ ，割掉了边 $x\to T,y\to T$

即 $VA_x+VA_y+VB_x+VB_y+EA_{x,y}+EB_{x,y}-c-d=VA_x+VA_y+EA_{x,y}$

那么 $VB_x+VB_y+EB_{x,y}=c+d$

如果 $x$ 和 $y$ 都在 $T$ ：价值为 $VB_x+VB_y+EB_{x,y}$ ，割掉了边 $S\to x,S\to y$

即 $VA_x+VA_y+VB_x+VB_y+EA_{x,y}+EB_{x,y}-a-b=VB_x+VB_y+EB_{x,y}$

那么 $VA_x+VA_y+EA_{x,y}=a+b$

如果 $x$ 在 $S$ ， $y$ 在 $T$ ：价值为 $VA_x+VB_y-EC_{x,y}$ ，割掉边 $S\to y,x\to y,x\to T$

即 $VA_x+VA_y+VB_x+VB_y+EA_{x,y}+EB_{x,y}-b-e-c=VA_x+VB_y-EC_{x,y}$

那么 $VA_y+VB_x+EA_{x,y}+EB_{x,y}+EC_{x,y}=b+e+c$

如果 $x$ 在 $T$ ， $y$ 在 $S$ ：价值为 $VB_x+VA_y-EC_{x,y}$ ，割掉边 $S\to x,y\to x,x\to T$

即 $VA_x+VA_y+VB_x+VB_y+EA_{x,y}+EB_{x,y}-a-f-d=VB_x+VA_y-EC_{x,y}$

那么 $VA_x+VB_y+EA_{x,y}+EB_{x,y}+EC_{x,y}=a+f+d$

这个方程有无穷多组解，然而由于 $x$ 和 $y$ 对称，所以结出来的结果是：

$a=VA_x+\frac 1 2EA_{x,y},b=VA_y+\frac 1 2 EA_{x,y}$

$c=VB_x+\frac 1 2EB_{x,y},d=VB_y+\frac 1 2 EB_{x,y}$

$e=f=\frac 1 2 EA_{x,y}+\frac 1 2EB_{x,y}+EC_{x,y}$

按这个把边权放大 $2$ 倍建图即可。