BZOJ1449[JSOI2009]球队收益&BZOJ2895球队预算——最小费用最大流

时间：2022-11-04 10:28:02

题目描述

BZOJ1449[JSOI2009]球队收益&BZOJ2895球队预算——最小费用最大流

输入

BZOJ1449[JSOI2009]球队收益&BZOJ2895球队预算——最小费用最大流

输出

一个整数表示联盟里所有球队收益之和的最小值。

样例输入

3 3
1 0 2 1
1 1 10 1
0 1 3 3
1 2
2 3
3 1

样例输出

43

提示

BZOJ1449[JSOI2009]球队收益&BZOJ2895球队预算——最小费用最大流

要求总费用最低考虑最小费用最大流。对于一场比赛同时决策两支队伍谁输谁赢不好办，我们先假设剩下的比赛每支队伍都输了，这样每次只要决策谁赢了即可。对于每次比赛将源点连向比赛，流量为$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)$，因为$D\le 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);

}

相关文章