题目描述
输入
输出
一个整数表示联盟里所有球队收益之和的最小值。
样例输入
3 3
1 0 2 1
1 1 10 1
0 1 3 3
1 2
2 3
3 1
1 0 2 1
1 1 10 1
0 1 3 3
1 2
2 3
3 1
样例输出
43
提示
要求总费用最低考虑最小费用最大流。对于一场比赛同时决策两支队伍谁输谁赢不好办，我们先假设剩下的比赛每支队伍都输了，这样每次只要决策谁赢了即可。对于每次比赛将源点连向比赛，流量为$1$、费用为$0$；再将比赛连向两支队伍，流量为$1$、费用为$0$。假设每支队伍还有$k[i]$场比赛，那么就将这只队伍向汇点连$k[i]$条边，流量为$1$，每条边费用为多赢一次的收益。每支队伍的起始收益为$C[i]*x^2+D[i]*y^2,x=win[i],y=lose[i]+k[i]$，每多赢一次的收益为$C*(x+1)^2+D*(y-1)^2-C*x^2-D*y^2=C*(2x+1)-D*(2y-1)$，因为$Dle C$，所以每多赢一次的收益会单调递增，又因为是最小费用最大流，所以一定先选赢一次的边、再选赢两次的边、再选赢三次的边……
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define INF 10000000
using namespace std;
int head[10000];
int next[20000];
int to[20000];
int v[20000];
int c[20000];
int f[10000];
int from[20000];
int tot=1;
int S,T;
ll ans;
int n,m;
int x,y;
int s[10000];
int win[10000];
int lose[10000];
int C[10000];
int D[10000];
queue<int>q;
int vis[10000];
int d[10000];
void add(int x,int y,int z,int w)
{
next[++tot]=head[x];
head[x]=tot;
to[tot]=y;
v[tot]=z;
c[tot]=w;
from[tot]=x;
next[++tot]=head[y];
head[y]=tot;
to[tot]=x;
v[tot]=-z;
c[tot]=0;
from[tot]=y;
}
void result()
{
int now=T;
int flow=INF;
while(now!=S)
{
flow=min(flow,c[f[now]]);
now=from[f[now]];
}
ans+=1ll*d[T]*flow;
now=T;
while(now!=S)
{
c[f[now]]-=flow;
c[f[now]^1]+=flow;
now=from[f[now]];
}
}
bool SPFA()
{
for(int i=1;i<=T;i++)
{
d[i]=INF;
}
d[S]=0;
q.push(S);
vis[S]=1;
while(!q.empty())
{
int now=q.front();
q.pop();
vis[now]=0;
for(int i=head[now];i;i=next[i])
{
if(!c[i])
{
continue;
}
if(d[to[i]]>d[now]+v[i])
{
d[to[i]]=d[now]+v[i];
f[to[i]]=i;
if(!vis[to[i]])
{
q.push(to[i]);
vis[to[i]]=1;
}
}
}
}
return d[T]!=INF;
}
void find_min()
{
while(SPFA())
{
result();
}
}
int main()
{
scanf("%d%d",&n,&m);
S=n+m+1;
T=S+1;
for(int i=1;i<=n;i++)
{
scanf("%d%d%d%d",&win[i],&lose[i],&C[i],&D[i]);
}
for(int i=1;i<=m;i++)
{
add(S,n+i,0,1);
scanf("%d%d",&x,&y);
s[x]++,s[y]++;
add(n+i,x,0,1);
add(n+i,y,0,1);
}
for(int i=1;i<=n;i++)
{
ans+=1ll*C[i]*win[i]*win[i]+1ll*D[i]*(lose[i]+s[i])*(lose[i]+s[i]);
x=win[i],y=lose[i]+s[i];
for(int j=1;j<=s[i];j++)
{
add(i,T,C[i]*(2*x+1)-D[i]*(2*y-1),1);
x++,y--;
}
}
find_min();
printf("%lld",ans);
}