Harmonious Army

Problem Description

Now, Bob is playing an interesting game in which he is a general of a harmonious army. There are n soldiers in this army. Each soldier should be in one of the two occupations, Mage or Warrior. There are m pairs of soldiers having combination ability. There are three kinds of combination ability. If the two soldiers in a pair are both Warriors, the army power would be increased by a . If the two soldiers in a pair are both Mages, the army power would be increased by c . Otherwise the army power would be increased by b , and b=a/4+c/3 , guaranteed that 4|a and 3|c . Your task is to output the maximum power Bob can increase by arranging the soldiers' occupations.

Note that the symbol a|b means that a divides b , e.g. , 3|12 and 8|24 .

Input

There are multiple test cases.

Each case starts with a line containing two positive integers n(n≤500) and m(m≤104) .

In the following m lines, each line contains five positive integers u,v,a,b,c (1≤u,v≤n,u≠v,1≤a,c≤4×106,b=a/4+c/3) , denoting soldiers u and v have combination ability, guaranteed that the pair (u,v) would not appear more than once.

It is guaranteed that the sum of n in all test cases is no larger than 5×103 , and the sum of m in all test cases is no larger than 5×104 .

Output

For each test case, output one line containing the maximum power Bob can increase by arranging the soldiers' occupations.

Sample Input

3 2

1 2 8 3 3

2 3 4 3 6

Sample Output

12

Source

2019 Multi-University Training Contest 2

Recommend

liuyiding   |   We have carefully selected several similar problems for you:  6602 6601 6600 6599 6598 

 题意：

n个士兵  m 个组合  

每个士兵可以转职战士或者魔法师

u  和  v  组合  两个战士战力+a   两个法师战力+c  其他战力+b

求最多加多少战力

题解很详细

化方案的权值为图上边权 利用最小割模型求解

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll maxn=505;
const ll maxm=5e5+12;
const ll inf=1e15;

struct Edge
{
    ll to,nxt;
    ll cap,flow;
}edge[maxm];
ll tol;
ll head[maxn];
ll Q[maxn];
ll dep[maxn],cur[maxn],sta[maxn];
void init()
{
    tol=0;
    memset(head,-1,sizeof(head));
    memset(dep,0,sizeof(dep));
    memset(cur,0,sizeof(cur));
    memset(sta,0,sizeof(sta));
    memset(edge,0,sizeof(edge));
}
void AddEdge(ll u,ll v,ll w,ll rw=0)
{
    edge[tol].to=v;
    edge[tol].cap=w;
    edge[tol].flow=0;
    edge[tol].nxt=head[u];
    head[u]=tol++;
    edge[tol].to=u;
    edge[tol].cap=rw;
    edge[tol].flow=0;
    edge[tol].nxt=head[v];
    head[v]=tol++;
}
bool bfs(ll s,ll t,ll n)
{
    ll front=0,tail=0;
    memset(dep,-1,sizeof(dep));
    dep[s]=0;
    Q[tail++]=s;
    while(front<tail)
    {
        ll u=Q[front++];
        for(ll i=head[u];i!=-1;i=edge[i].nxt)
        {
            ll v=edge[i].to;
            if(edge[i].cap>edge[i].flow&&dep[v]==-1)
            {
                dep[v]=dep[u]+1;
                if(v==t)
                    return true;
                Q[tail++]=v;
            }
        }
    }
    return false;
}
ll dinic(ll s,ll t,ll n)
{
    ll maxflow=0;
    while(bfs(s,t,n))
    {
        for(ll i=0;i<n;i++)
            cur[i]=head[i];
        ll u=s,tail=0;
        while(cur[s]!=-1)
        {
            if(u==t)
            {
                ll tp=inf;
                for(ll i=tail-1;i>=0;i--)
                {
                    tp=min(tp,edge[sta[i]].cap-edge[sta[i]].flow);
                }
                maxflow+=tp;
                for(ll i=tail-1;i>=0;i--)
                {
                    edge[sta[i]].flow+=tp;
                    edge[sta[i]^1].flow-=tp;
                    if(edge[sta[i]].cap-edge[sta[i]].flow==0)
                        tail=i;
                }
                u=edge[sta[tail]^1].to;
            }
            else if(cur[u]!=-1&&edge[cur[u]].cap>edge[cur[u]].flow&&dep[u]+1==dep[edge[cur[u]].to])
            {
                sta[tail++]=cur[u];
                u=edge[cur[u]].to;
            }
            else
            {
                while(u!=s&&cur[u]==-1)
                    u=edge[sta[--tail]^1].to;
                cur[u]=edge[cur[u]].nxt;
            }
        }
    }
    return maxflow;
}
int main()
{
    ll m,n;
    while(~scanf("%lld%lld",&n,&m))
    {
        init();
        ll u,v,a,b,c;
        ll A,C,E;
        ll s=0,t=n+1;
        ll sum=0;
        for(int cas=1;cas<=m;cas++)
        {
            scanf("%lld%lld%lld%lld%lld",&u,&v,&a,&b,&c);
            a*=2;
            b*=2;
            c*=2;
            sum+=a+b+c;
            A=(a+b)/2;
            C=(c+b)/2;
            E=-b+(a+c)/2;
            AddEdge(s,u,A);
            AddEdge(s,v,A);
            AddEdge(u,t,C);
            AddEdge(v,t,C);
            AddEdge(u,v,E);
            AddEdge(v,u,E);
        }
        ll ans=dinic(s,t,n+2);
        printf("%lld\n",(sum-ans)/2);
    }
}