Harmonious Army

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1539 Accepted Submission(s): 557

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

对于每个士兵非黑即白（也就是要么法师，要么战士），但是这道题和其他不一样，这道题有三种价值，而且只有组合才会产生价值。

考虑最小割建图：也就是考虑士兵的集合划分，对于两边的划分，分别算出割掉的价值即可，然后最小割，用所有价值减去最小割即为答案。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1010,M=1e6+10;
int n,m,h[N],s,t,res;
int head[N],nex[M],to[M],w[M],tot;
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 void init(){
	res=0; memset(head,0,sizeof head); tot=1; t=n+1;
}
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(!h[to[i]]&&w[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(h[to[i]]==h[x]+1&&w[i]){
			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;
}
int dinic(){
	int res=0;
	while(bfs())	res+=dfs(s,0x3f3f3f3f);
	return res;
}
signed main(){
	while(~scanf("%lld %lld",&n,&m)){
		init();
		for(int i=1;i<=m;i++){
			int u,v,a,b,c;	scanf("%lld %lld %lld %lld %lld",&u,&v,&a,&b,&c);
			a*=2; b*=2; c*=2; res+=(a+b+c);
			add(s,u,5*a/8+c/6); add(s,v,5*a/8+c/6); add(u,v,a/4+c/6);
			add(v,u,a/4+c/6);	add(u,t,a/8+2*c/3); add(v,t,a/8+2*c/3);
		}
		printf("%lld\n",(res-dinic())/2);
	}
	return 0;
}