「JSOI2009」球队收益 / 球队预算

题目链接

戳我

\(Solution\)

我们发现这道题目并不好做，因为要考虑两个因素对答案的影响。于是我们假设接下来的\(m\)场比赛双方都输了。这要我们就只要考虑赢一场对答案的影响了,那每赢一场输的数量就会减少\(1\).所以我们来化简一下式子:

\(x\)为赢的数量，\(y\)为输的数量

我们对于这个发现不能直接的算贡献，于是直接拆边做费用流就好了,最后答案就是全输之后的答案加上费用流即可

\(Code\)

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int read(){

    int x=0,f=1;

    char c=getchar();

    while(c<'0'||c>'9')

        f=(c=='-')?-1:1,c=getchar();

    while(c>='0'&&c<='9')

        x=x*10+c-'0',c=getchar();

    return x*f;

}

struct node{

    int to,next,v,w;

}a[1000001];

int dis[10001],f[10001],pre[10001],fa[10001],s,t,n,m,head[10001],cnt,x,y,z,c,win[10001],lost[10001],vis[10001],C[10001],D[10001];

void add(int x,int y,int c,int v){

	a[++cnt].to=y,a[cnt].next=head[x],a[cnt].v=c,a[cnt].w=v,head[x]=cnt;

	a[++cnt].to=x,a[cnt].next=head[y],a[cnt].v=0,a[cnt].w=-v,head[y]=cnt;

}

queue < int > q;

int spfa(){

    q.push(s);

    memset(dis,127,sizeof(dis));

    memset(f,0,sizeof(f));

    f[s]=1,dis[s]=0;

    int inf=dis[s+1];

    while(!q.empty()){

        int now=q.front();

        q.pop();

        f[now]=0;

        for(int i=head[now];i;i=a[i].next){

            int v=a[i].to;

            if(dis[v]>dis[now]+a[i].w&&a[i].v){

                dis[v]=dis[now]+a[i].w,pre[v]=i,fa[v]=now;

                if(!f[v])

                    f[v]=1,q.push(v);

            }

        }

    }

    if(dis[t]!=inf)

        return 1;

    return 0;

}

int ans1,ans,res;

void answer(){

    while(spfa()){

        int minx=2147483647;

        for(int i=t;i!=s;i=fa[i])

            minx=min(minx,a[pre[i]].v);

        ans+=minx,ans1+=dis[t]*minx;

        for(int i=t;i!=s;i=fa[i])

            a[pre[i]].v-=minx,(pre[i]%2)?a[pre[i]+1].v+=minx:a[pre[i]-1].v+=minx;

    }

}

int main(){

    n=read(),m=read(),s=0,t=n+m+1;

	for(int i=1;i<=n;i++)

		win[i]=read(),lost[i]=read(),C[i]=read(),D[i]=read();

	for(int i=1;i<=m;i++)

		x=read(),y=read(),add(s,i,1,0),add(i,x+m,1,0),add(i,y+m,1,0),vis[x]++,vis[y]++;

	for(int i=1;i<=n;i++)

		lost[i]+=vis[i],res+=C[i]*win[i]*win[i]+D[i]*lost[i]*lost[i];

	for(int i=1;i<=n;i++)

		for(int j=1;j<=vis[i];j++)

			add(i+m,t,1,C[i]*win[i]*2-D[i]*lost[i]*2+C[i]+D[i]),lost[i]--,win[i]++;

    answer();

    printf("%d",res+ans1);

}