题目链接：小D的剑阵

对每一个东西就是选不选的问题。

也就是非黑即白的问题，于是我们可以想到最小割。

图片说明

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e3+10,M=1e6+10;
int s,t,n,q,h[N],res,val[N];
int head[N],nex[M],to[M],w[M],tot=1;
inline void ade(int a,int b,int c){
    to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;
}
inline void add(int a,int b,int c){ade(a,b,c);  ade(b,a,0);}
inline int bfs(){
    queue<int> q;   q.push(s);  memset(h,0,sizeof h); h[s]=1;
    while(q.size()){
        int u=q.front();    q.pop();
        for(int i=head[u];i;i=nex[i]){
            if(w[i]&&!h[to[i]]){
                h[to[i]]=h[u]+1;    q.push(to[i]);
            }
        }
    }
    return h[t];
}
int dfs(int x,int f){
    if(x==t)    return f;   int fl=0;
    for(int i=head[x];i&&f;i=nex[i]){
        if(w[i]&&h[to[i]]==h[x]+1){
            int mi=dfs(to[i],min(w[i],f));
            w[i]-=mi,w[i^1]+=mi,fl+=mi,f-=mi;
        }
    }
    if(!fl) h[x]=-1;
    return fl;
}
inline int dinic(){
    int res=0;
    while(bfs())    res+=dfs(s,inf);
    return res;
}
int main(){
    cin>>n>>q; t=n+1;
    for(int i=1;i<=n;i++)   cin>>val[i],res+=val[i];
    while(q--){
        static int x,y,v0,v1,v2;    cin>>x>>y>>v0>>v1>>v2;
        res+=v0; res+=v1; val[x]+=v0/2; val[y]+=v0/2;
        add(x,t,v1/2);  add(y,t,v1/2);
        add(x,y,v2+(v0+v1)/2);  add(y,x,v2+(v0+v1)/2);
    }
    for(int i=1;i<=n;i++)   add(s,i,val[i]);
    cout<<res-dinic()<<endl;
    return 0;
}