题意：有n个人两种职业可供选择，有m对选择的关系，当两个人同时选择第一种职业时，将会获得a的权值,都选择第二种职业时将会获得c的权值，两人职业不同时将会获得的权值。让你为每个人分配职业，使得全职总和最大。
既然有两种职业，当然不难想到二分图。
一个人可选择两种职业，考虑拆点，拆成战士和法师两个部分。思考了一阵觉得没法使用最大流模型计算，考虑转化为最小割。
一开始，假设每个人既可以当法师，也可以当战士（当然，实际上不存在这种情况），那么你就可以获得的价值。

先大概在纸上建一个草图，如图所示，每个人拆成两个点分别表示他是战士还是法师，然后限制条件是一个人只能有一种身份，所以他要么舍弃他法师的身份，要么舍弃他战士的身份。
用最小割表示最小舍。
为了限制他，使其必须舍弃其中一种身份，所以将二分图中连向自己的边设为inf。
我们设两个人都选择第一种身份的时候获得a，都选择第二种身份的时候获得c。
那么对于这四个点的最小割只有三种情况“：
1、当两个人都选择第一种身份的时候这两个点就会割掉权值为c的边。
2、当两个人都选择第二种身份的时候这两个点就会割掉权值为a的边。
3、问题是这两个人一个选择第一种身份一个选择第二种身份的时候一个会割掉a，一个会割掉c，然后呢？

用瞪眼法可知在这种情况下一定还会再割掉中间的一条边，为什么？
可以使用反证法，若它不割掉中间的边，它只能选择再割掉另外两条a,c边，这样相当于全部割掉（割为2a+2c），但是我们知道至少存在一个割是2a或者2c，这两个割都小于2a+2c，即2a+2c不是最小割，所以这种情况不在最小割上。反证的证，说明若一个割掉a，一个割掉c，另一个割边一定为中间的边。我们只用考虑这条边的边权即可。
在这种情况下，我们已经割掉了a+c的权值，而实际上我们应该令这种情况获得的权值等于2b，也就是。
设这条边的权值为x，解方程。
解得
所以中间这条边的权值为。

最后的网络如图所示，然后答案等于 
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAXN=300005,MAXM=500005<<1;
const long long INF=(1LL<<60);
int g[MAXN];
struct edges
{
    int to,next;
    long long cap,flow;
} e[MAXM];
int tot=1,head,tail,q[MAXN],dis[MAXN],vist[MAXN],s,t,maxp,temp[MAXN];
long long min1(long long a1,long long b1)
{
    return a1<b1?a1:b1;
}
void adds(int a1,int b1,long long c1)
{
    tot++;
    e[tot].to=b1;
    e[tot].cap=c1;
    e[tot].next=g[a1];
    e[tot].flow=0;
    g[a1]=tot;
    return;
}
void add_edge(int a1,int b1,long long c1)
{
    adds(a1,b1,c1);
    adds(b1,a1,0);
    return;
}
bool bfs()
{
    for(int i=0; i<=maxp; i++)
    {
        vist[i]=false;
    }
    head=0;
    tail=1;
    q[tail]=s;
    vist[s]=true;
    while(head!=tail)
    {
        head++;
        int x=q[head];
        for(int i=g[x]; i; i=e[i].next)
        {
            if(e[i].cap>e[i].flow&&!vist[e[i].to])
            {
                tail++;
                q[tail]=e[i].to;
                vist[e[i].to]=true;
                dis[e[i].to]=dis[x]+1;
            }
        }
    }
    return vist[t];
}
long long dfs(int now,long long mins)
{
    if(now==t||mins==0)return mins;
    long long now_flow=0,next_flow;
    for(; temp[now]; temp[now]=e[temp[now]].next)
    {
        if(dis[e[temp[now]].to]==dis[now]+1)
        {
            next_flow=dfs(e[temp[now]].to,min1(mins,e[temp[now]].cap-e[temp[now]].flow));
            if(next_flow>0)
            {
                e[temp[now]].flow+=next_flow;
                e[temp[now]^1].flow-=next_flow;
                now_flow+=next_flow;
                mins-=next_flow;
                if(mins==0)
                break;
            }
        }
    }
    return now_flow;
}
long long dinic()
{
    long long ans=0;
    while(bfs())
    {
        for(int i=0; i<=maxp; ++i)
        {
            temp[i]=g[i];
        }
        ans+=dfs(s,INF);
    }
    return ans;
}
void init()
{
    memset(g,0,sizeof(g));
    tot=1;
    return;
}
int T,n,m,u,v;
long long val[MAXN],ans,a,b,c;
int main()
{
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        ans=0;
        for(int i=1;i<=2*n;++i)
        {
            val[i]=0;
        }
        s=2*n+1;
        t=2*n+2;
        maxp=t;
        init();
        for(int i=1;i<=m;++i)
        {
            scanf("%d %d %lld %lld %lld",&u,&v,&a,&b,&c);
            val[u]+=a;
            val[v]+=a;
            val[n+u]+=c;
            val[n+v]+=c;
            add_edge(u,n+v,a/2+c/3);
            add_edge(v,n+u,a/2+c/3);
            ans+=a*2+c*2;
        }
        for(int i=1;i<=n;++i)
        {
            add_edge(i,n+i,INF);
            add_edge(s,i,val[i]);
            add_edge(n+i,t,val[n+i]);
        }
        printf("%lld\n",(ans-dinic())/2);
    }
    return 0;
}