Harmonious Army
时间限制: 1 Sec 内存限制: 128 MB
题目描述
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.
输入
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.
输出
For each test case, output one line containing the maximum power Bob can increase by arranging the soldiers‘ occupations.
样例输入
3 2
1 2 8 3 3
2 3 4 3 6
样例输出
12
题意：给n个士兵安排两种职业，有m个关系，关系的贡献与该关系两边的士兵的职业有关，求最大贡献和。
最小割建图好题，Mark一下。思路参考题解：
对每个士兵建立一个点x ，点x 向源点s 连一条边，向汇点t 连一条边，分别表示选择两种职业，然后就可以先加上所有的贡献，通过两点关系用最小割建模，如下图所示。
设一条边的三种贡献为A;B;C，可以得到以下方程：
a+b=A+B(x,y都选Mage)
c+d=C+B(x,y都选Warrior)
a+d+e=A+C(x选Mage,y选Warrior)
b+c+e=A+C(x选Warrior,y选Mage)
可得一组解a=b=(A+B)/2,c=d=(C+B)/2,e=-B+(A+C)/2，然后将所有有关系的两点的图合并，用所有贡献减掉这个图的最小割即可。
#include<bits/stdc++.h>
#define N 505
using namespace std;
typedef struct
{
int to,next;
long long flow;
}ss;
ss edg[N*N];
int now_edge=0,s,t;
int head[N];
void addedge(int u,int v,long long flow)
{
edg[now_edge]=(ss){v,head[u],flow};
head[u]=now_edge++;
edg[now_edge]=(ss){u,head[v],0};
head[v]=now_edge++;
}
int dis[N];
bool bfs()
{
memset(dis,0,sizeof(dis));
queue<int>q;
q.push(s);
dis[s]=1;
while(!q.empty())
{
int now=q.front();
q.pop();
for(int i=head[now];i!=-1;i=edg[i].next)
{
ss &e=edg[i];
if(e.flow>0&&dis[e.to]==0)
{
dis[e.to]=dis[now]+1;
q.push(e.to);
}
}
}
if(dis[t]==0)return 0;
return 1;
}
int current[N];
long long dfs(int x,long long maxflow)
{
if(x==t)return maxflow;
// printf("%d %lld\n",x,maxflow);
for(int i=current[x];i!=-1;i=edg[i].next)
{
current[x]=i;
ss &e=edg[i];
if(e.flow>0&&dis[e.to]==dis[x]+1)
{
long long flow=dfs(e.to,min(maxflow,e.flow));
if(flow!=0)
{
e.flow-=flow;
edg[i^1].flow+=flow;
return flow;
}
}
}
return 0;
}
long long dinic()
{
long long ans=0,flow;
while(bfs())
{
for(int i=0;i<N;i++)current[i]=head[i];
while(flow=dfs(s,LLONG_MAX/2))ans+=flow;
}
return ans;
}
void init()
{
for(int i=0;i<N;i++)head[i]=-1;
now_edge=0;
}
int Map[N][N];
int main()
{
int n,m;
while(scanf("%d %d",&n,&m)==2)
{
init();
for(int i=0;i<=n+2;i++)
for(int j=0;j<=n+2;j++)Map[i][j]=0;
long long ans=0;
s=n+1;
t=s+1;
while(m--)
{
int u,v,a,b,c;
scanf("%d %d %d %d %d",&u,&v,&a,&b,&c);
ans+=a+b+c;
Map[s][u]+=a+b;
Map[s][v]+=a+b;
Map[u][t]+=c+b;
Map[v][t]+=c+b;
Map[u][v]+=a+c-2*b;
Map[v][u]+=a+c-2*b;
}
for(int i=1;i<=n+2;i++)
for(int j=1;j<=n+2;j++)if(Map[i][j])addedge(i,j,Map[i][j]);
printf("%lld\n",ans-dinic()/2);
}
return 0;
}
View Code
Harmonious Army
原文：https://www.cnblogs.com/tian-luo/p/11240796.html
