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}\) 。
也就是说:
-
对于 \(i\) 球队赢的点 入点向出点建 \(sum_i\) (表示这个球队参与了多少场比赛)条边,对于第 \(j\) 条边,建一条容量为 \(1\) 费用为 \(c_i\times((j+a_i-1)\times+1)\) 的边。
-
对于 \(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