首页 > 其他分享 >【题解】P4307 [JSOI2009] 球队收益 / 球队预算

【题解】P4307 [JSOI2009] 球队收益 / 球队预算

时间:2024-04-16 18:59:21浏览次数:27  
标签:int 题解 JSOI2009 edge cost 球队 lim sum

P4307 [JSOI2009] 球队收益 / 球队预算 题解

题目传送门

题意简述

一共有 \(n\) 个球队比赛,输了赢了都会有相应的支出,现在让你安排 \(m\) 场比赛的输赢,是总支出最少。

思路

首先看到最小支出,状态不好定义,直接 费用流,启动!

后文如果没有特殊说明,边的费用均为 \(0\) 。

考虑建图,其他大佬建图方式太神了 \(\texttt{sto\%\%\%orz}\) ,我提供一种非常好想的建图方式。

首先,一共 \(m\) 场比赛,对于第 \(i\) 场比赛,我们要分配到底是哪一方赢 (后文用 \(s\) 和 \(t\) 表示这两个球队)。

由于输和赢的代价不好一起表示,所以将每个球队 \(i\) 考虑拆为两个点 \(i_{win}\) 和 \(i_{los}\) 。

考虑新建两个节点 \(m_i\) 和 \(m_i'\) ,然后从源点向 \(m_i\) 和 \(m_i'\) 分别连容量 \(1\) 的边。

从 \(m_i\) 向 \(s_{win}\) , \(t_{win}\) 连容量为 \(1\) 的边。

从 \(m_i'\) 向 \(s_{los}\) , \(t_{los}\) 连容量为 \(1\) 的边。

这样我们就控制了每场比赛必然有一方赢,一方输 (并不是一方赢,一方输)。

但我们会发现,可能会出现 \(s\) 赢的同时 \(s\) 也输了这种情况,所以,我们还得限制这种情况。

考虑在建两个新点 \(o_s\) 和 \(o_t\) ,然后分别从 \(s_{win}\) 和 \(s_{los}\) 向 \(o_s\) 连容量为 \(1\) 的边,\(t_{win}\) 和 \(t_{los}\) 向 \(o_t\) 连容量为 \(1\) 的边。

这样我们从两个方面分别限制,就只会出现一方赢,一方输的情况了。

比赛建完,现在考虑支出。

不好求点的代价怎么办,拆!

现在就相当于把每个球队 \(i\) 拆成了四个点 (不会其他的建图,没法啊),赢的点拆成入和出,输的点拆成入和出。

处理入点和出点间平方的费用,直接上公式 \(n^2=\sum\limits_{i=1}^n{2\times i-1}\) 。

也就是说:

  1. 对于 \(i\) 球队赢的点 入点向出点建 \(sum_i\) (表示这个球队参与了多少场比赛)条边,对于第 \(j\) 条边,建一条容量为 \(1\) 费用为 \(c_i\times((j+a_i-1)\times+1)\) 的边。

  2. 对于 \(i\) 球队输的点 入点向出点建 \(sum_i\) 条边,对于第 \(j\) 条边,建一条容量为 \(1\) 费用为 \(d_i\times((j+b_i-1)\times+1)\) 的边。

最后跑最小费用最大流,答案为 \(最小费用+\sum\limits_{i=1}^n{c_i\times a_i^2 +d_i\times b_i^2}\) 。

代码

#include<bits/stdc++.h>
using namespace std;
const int MX_N=50100,MX_M=5000100;
const int INF=0x3f3f3f3f;
struct node{
    int to,next;
    int w,cost;
}edge[MX_M<<1];
int head[MX_N]={0},edge_cnt=0;
inline void Add(int x,int y,int w,int c){
    node& it=edge[edge_cnt];
    it.cost=c;it.next=head[x];it.w=w;it.to=y;
    head[x]=edge_cnt++;
}

inline void add(int x,int y,int w,int c){
    Add(x,y,w,c),Add(y,x,0,-c);
}
int s=0,t=MX_N-1;
int pre[MX_N]={0},lim[MX_N]={0},dist[MX_N]={0};
bool vis[MX_N]={0};
bool spfa(){
    memset(lim,0,sizeof(lim));memset(dist,INF,sizeof(dist));memset(vis,0,sizeof(vis));
    queue<int >qu;
    qu.push(s);lim[s]=INF,vis[s]=1,dist[s]=0;
    while(!qu.empty()){
        int now=qu.front();qu.pop();vis[now]=0;
        for(int i=head[now];~i;i=edge[i].next){
            int to=edge[i].to,w=edge[i].w,cost=edge[i].cost;
            if(w&&dist[to]>dist[now]+cost){
                dist[to]=dist[now]+cost;
                pre[to]=i;
                lim[to]=min(lim[now],w);
                if(!vis[to]){
                    qu.push(to);
                    vis[to]=1;
                }
            }
        }
    }
    return lim[t]>0;
}
void EK(int &flow,int &cost){
    flow=cost=0;
    while(spfa()){
        flow+=lim[t];
        cost+=lim[t]*dist[t];
        for(int i=t;i!=s;i=edge[pre[i]^1].to){
            edge[pre[i]].w-=lim[t];
            edge[pre[i]^1].w+=lim[t];
        }
    }
}
int n,m;
int tot[5010]={0};
int ai[5010]={0},bi[5010]={0},ci[5010]={0},di[5010]={0};
inline int has(int x,bool sf,bool io){
    int sum=4*m;
    if(sf==1&&io==0)  return sum+x;
    if(sf==1&&io==1)  return sum+x+n;
    if(sf==0&&io==0)  return sum+x+n+n;
    if(sf==0&&io==1)  return sum+x+n+n+n;
}
signed main(){
    memset(head,-1,sizeof(head));
    //=======================================
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d%d",ai+i,bi+i,ci+i,di+i);
    }
    for(int i=1;i<=m;i++){
        int x,y;scanf("%d%d",&x,&y);
        tot[x]++,tot[y]++;
        add(s,i,1,0),add(s,i+m,1,0);

        add(i,has(x,1,0),1,0),add(i,has(y,1,0),1,0);
        add(i+m,has(x,0,0),1,0),add(i+m,has(y,0,0),1,0);

        add(has(x,1,1),i+m+m,1,0),add(has(x,0,1),i+m+m,1,0);
        add(has(y,1,1),i+m+m+m,1,0),add(has(y,0,1),i+m+m+m,1,0);

        add(i+m+m,t,1,0),add(i+m+m+m,t,1,0);
    }
    int sumn=0;
    for(int i=1;i<=n;i++){
        sumn+=ci[i]*(ai[i]*ai[i])+di[i]*(bi[i]*bi[i]);
        for(int k=0;k<=tot[i];k++){
            add(has(i,1,0),has(i,1,1),1,ci[i]*((k+ai[i])*2+1));
            add(has(i,0,0),has(i,0,1),1,di[i]*((k+bi[i])*2+1));
        }
    }
    int flow,cost;EK(flow,cost);
    printf("%d",sumn+cost);
    //=======================================
    return 0;
}

标签:int,题解,JSOI2009,edge,cost,球队,lim,sum
From: https://www.cnblogs.com/DaiFu/p/18138945

相关文章

  • ABC263Ex Intersection 2 题解
    ABC263ExProblem给定\(N\)条不平行的直线\(A_ix+B_iy+C=0\),\(N\)条直线总共会有\(\frac{N(N-1)}{2}\)个交点(包含在同一个位置的点,即相同位置算不同的点),找出距离原点第\(K\)近的交点的距离。$2\leN\le5\times10^4$,\(1\leK\le\frac{N(N-1)}{2}\),$-1000\le|A_i|,|B_......
  • CF154C Double Profiles 题解
    CF154CDoubleProfiles题解思路解析题目说的很明白,求有多少个无序点对\((i,j)\),使得与\(i\)直接相连的点集与直接与\(j\)相连的点集完全相等。我们想到如果直接判断每个\(i,j\)肯定会超时,所以我们想把每一个与任意一点直接相连的点集进行压缩,可以想到使用字符串哈希的......
  • [题解] [CCPC陕西省赛2022 D题] Hash
    [CCPC陕西省赛2022D题]Hash题目描述给定一个字符串\(S\),按照如下方法获取\(S\)的哈希值://LanguageC++14longlongmod=5999993;longlonggethas(strings){longlongret=0;for(charc:s)ret=(ret*29+(c-'a'+1))%mod;returnret;}找到一个......
  • CF1097F Alex and a TV Show 题解
    题目链接点击打开链接题目解法很牛的套路啊!看到集合并,且只要求奇偶性的问题,第一个想到\(bitset\)\(1,2,4\)操作都是好维护的,关键是第\(3\)个操作看到$\gcd$,首先想到莫反令\(c_{x,i}\)为集合\(x\)中数\(i\)的出现次数则\(c_{x,i}=\sum\limits_{i|j}\sum\limit......
  • 如何写好一篇题解?
    为什么要写题解?首先要清楚知道一点,写题解不仅是帮助别人在做题遇到困难时指明方向,更是提升自己的最快途径。经常有人问我:“如何提升自己的程序设计能力”。我都会回答:“写题解”。写题解可以帮助你彻底掌握某一个知识点。无论一道题目是否是你独立写出来的,你都应该去尝试写题解......
  • 取胜 题解
    很厉害的题,记录下题意是随机一棵无根树,随一个根,每条边存在(能走通)的概率为\(p\),以根为起点,每次一方选择当前点的一个能走通的儿子走过去,问先手必胜的概率.容易发现可以当成有根树.用\(F(x)\)和\(G(x)\)表示必胜树和必败树的egf,有\[\begin{cases}F(x)=xe^{F(x)}\le......
  • 开机后mysql服务未启动问题解决
    问题:mysql的启动类型设置了自动,但是电脑开机后还是需要手动启动。 解决方法:一、Win+R快捷键弹出运行框 二、输入regedit后回车 三、地址栏内输入计算机\HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control后回车 四、找到Control入径后,新建一个名称为ServicesPipe......
  • [题解][2021-2022年度国际大学生程序设计竞赛第10届陕西省程序设计竞赛] Type The Str
    题目描述给定n个字符串,有以下几种操作:打出一个字符,花费1。删除一个字符,花费1。复制并打出一个之前打出过的字符串,花费k。求打出所有n个字符串的最小花费。(注意,打出顺序和字符串输入的顺序不必相同)题解显然,操作3需要算字符串的最长公共子序列来处理。这个问题可以转换为......
  • P4298 [CTSC2008] 祭祀 题解
    P4298[CTSC2008]祭祀题解给定DAG,求最长反链长度,最长反链方案,有多少个点可以成为反链上的点。Case1熟知Dilworth定理:偏序集的最长反链的长度等于最小链划分。因为偏序集有传递性,所以我们也需要对DAG做一遍传递闭包。这样可以套用Dilworth定理,最小链划分等于点数减......
  • [题解][2021-2022年度国际大学生程序设计竞赛第10届陕西省程序设计竞赛] Hash
    题目描述给定字符串T,要求求字符串S,满足以下条件:S是T的前缀S和T运行某段代码的哈希值相同(代码见下)T只包含小写字母S和T的长度差不超过50哈希代码://LanguageC++14longlongmod=5999993;longlonggethas(strings){longlongret=0;for(charc:s)ret=......