题意概述：
有N个人，A,B两个考场。如果学生i在A考场，总信心值增加xi；如果学生i在B考场，总信心值增加yi。其中还有m对好友，当第i对好友的两个人都在A考场时，总信心值增加ai；如果两人都在B考场，总信心值增加bi；如果两个人在不同考场，那么总信心值减少ci。
问总信心值最大能达到多少（总信心值的初始值为0）。
N<=10000,M<=50000,time limit = 1s
分析：
这类最小割问题非常经典，一般都是有两个集合，每个元素属于某个集合可以得到某种收益，同时还会有一些两个元素之间的关系，比如被分到同一个集合或者不同集合需要付出的代价/得到的收益等等。思路是首先我们将所有的收益全部加起来，假设我们得到了所有的收益，然后建图跑最小割求我们需要付出的最小代价，最大收益=所有可能的收益-最小代价。
说一下此题的建图，此题本身选择就可能产生代价，因此把代价看成收益。假设我们一开始从获得的总收益为，所有的x,y,a,b,c的和。
令s代表B考场，t代表A考场，s向所有考生连边容量为yi，当这条边被割掉的时候考生i被选入A考场，付出代价yi；所有考生向t连一条边容量为xi，意义同上；所有的朋友之间，s向两个点分别连边，容量为(b+c)/2，当这两条边被一起割掉的时候他们都在A考场，付出代价b+c；两个点向t连边，意义类似；两个点之间连一条容量为(a+b+2c)/2，当两个考生在不同考场的时候（在网络意义下他们不连通）这条边被割掉，这对朋友一共付出代价a+b+2c。
跑最小割即可，因为建图的时候涉及到除以二的问题所以先把所有的边容量乘以2，最后把这个2除回来即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<cctype>
#define inf 9e18
using namespace std;
const int maxn=;
const int maxm=;
typedef long long LL; int N,M,A[maxn],B[maxn],S,T,tot;
struct data{ int u,v,a,b,c; }C[maxm];
struct net_edge{ int from,to,next; LL cap,flow; }NE[*maxn+*maxm];
int nfirst[maxn],nnp,cur[maxn],fl[maxn],d[maxn],gap[maxn];
int mq[maxn],front,rear; void _scanf(int &x)
{
x=;
char ch=getchar();
while(ch<''||ch>'') ch=getchar();
while(ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
}
void data_in()
{
_scanf(N);_scanf(M);
for(int i=;i<=N;i++) _scanf(A[i]);
for(int i=;i<=N;i++) _scanf(B[i]);
for(int i=;i<=M;i++){
_scanf(C[i].u);_scanf(C[i].v);
_scanf(C[i].a);_scanf(C[i].b);_scanf(C[i].c);
}
}
void net_add_edge(int u,int v,LL cap)
{
NE[++nnp]=(net_edge){u,v,nfirst[u],cap,};
nfirst[u]=nnp;
NE[++nnp]=(net_edge){v,u,nfirst[v],,};
nfirst[v]=nnp;
}
void _net_add_edge(int u,int v,LL cap)
{
NE[++nnp]=(net_edge){u,v,nfirst[u],cap,};
nfirst[u]=nnp;
NE[++nnp]=(net_edge){v,u,nfirst[v],cap,};
nfirst[v]=nnp;
}
void build_net()
{
S=N+,T=N+,tot=T;
for(int i=;i<=N;i++){
net_add_edge(S,i,(LL)*B[i]);
net_add_edge(i,T,(LL)*A[i]);
}
int u,v;
for(int i=;i<=M;i++){
u=C[i].u,v=C[i].v;
net_add_edge(S,u,(LL)C[i].b+C[i].c);
net_add_edge(u,T,(LL)C[i].a+C[i].c);
net_add_edge(S,v,(LL)C[i].b+C[i].c);
net_add_edge(v,T,(LL)C[i].a+C[i].c);
_net_add_edge(u,v,(LL)C[i].a+C[i].b+(LL)*C[i].c);
}
}
void BFS(int s)
{
for(int i=;i<=tot;i++) d[i]=tot;
front=rear=;
mq[rear++]=s;
d[s]=;
int i,j;
while(front!=rear){
i=mq[front++];
for(int p=nfirst[i];p;p=NE[p].next){
j=NE[p].to;
if(d[j]==tot) d[j]=d[i]+,mq[rear++]=j;
}
}
}
LL augment(int s,int t)
{
int now=t; LL flow=inf;
while(now!=s){
flow=min(flow,NE[fl[now]].cap-NE[fl[now]].flow);
now=NE[fl[now]].from;
}
now=t;
while(now!=s){
NE[fl[now]].flow+=flow,NE[(fl[now]-^)+].flow-=flow;
now=NE[fl[now]].from;
}
return flow;
}
LL ISAP(int s,int t)
{
memcpy(cur,nfirst,sizeof(cur));
BFS(t);
for(int i=;i<=tot;i++) gap[d[i]]++;
LL maxflow=; int now=s,j;
while(d[s]<tot){
if(now==t){
maxflow+=augment(s,t);
now=s;
}
bool ok=;
for(int p=cur[now];p;p=NE[p].next){
j=NE[p].to;
if(d[j]+==d[now]&&NE[p].cap>NE[p].flow){
ok=;
cur[now]=fl[j]=p;
now=j;
break;
}
}
if(!ok){
int minl=tot;
for(int p=nfirst[now];p;p=NE[p].next){
j=NE[p].to;
if(d[j]+<minl&&NE[p].cap>NE[p].flow) minl=d[j]+;
}
if(--gap[d[now]]==) break;
gap[d[now]=minl]++;
cur[now]=nfirst[now];
if(now!=s) now=NE[fl[now]].from;
}
}
return maxflow;
}
void work()
{
build_net();
LL sum=;
for(int i=;i<=N;i++) sum+=A[i],sum+=B[i];
for(int i=;i<=M;i++)
sum+=C[i].a,sum+=C[i].b,sum+=C[i].c;
cout<<sum-ISAP(S,T)/<<'\n';
}
int main()
{
data_in();
work();
return ;
}