自动搬运

查看原文

来自洛谷，原作者为

	Hyscere **

搬运于2025-08-24 21:58:47，当前版本为作者最后更新于2019-03-04 18:06:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

费用流。

对于每个球队设点$A_i$，每场未确定的比赛设$B_i$，那么有一个比较显然的框架：

• 对于每个点$A_i$，$A_i$到$t$连边，容量为剩下的场次中$i$最多可以赢的次数，这个次数设为$mx_i$。
• 对于每个点$B_i$，连边$(s,B_i),(B_i,x),(B_i,y)$，其中$x,y$表示这场比赛的双方，容量都为$1$。

很显然可以知道这个图的每一种最大流代表一种方案，现在我们的目的就是要给这个图的边加权，使得费用最小。

考虑一场比赛都没进行的时候（题目给出的结果不算），假设每支球队每场都输了，那么当前有一个总代价，然后比了一场比赛，那么必然就有一支球队输场$-1$，胜场$+1$，设原来赢了$a$场，输了$b$场，那么新增的代价就是：

注意到随着胜场的增多，败场的减小，这个式子是单调递增的，也就是说，我们可以利用拆边的思想建图。

那么建图修改为：

• 对于每个点$A_i$，向$t$连$mx_i$条边，容量为$1$，费用依次递增，也就是上面那个式子。
• 其他的边费用均为$0$。

然后跑最小费用最大流，加上已经确定的花费，就是总代价了。

#include<bits/stdc++.h>
using namespace std;
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define sqr(x) ((x)*(x))

const int maxn = 1e5+10;
const int inf = 1e9;

int n,m,s,t,tot=1,cost;
int head[maxn],vis[maxn],dis[maxn],a[maxn],b[maxn],C[maxn],D[maxn],l[maxn],fr[maxn],pre[maxn];
struct edge{int to,nxt,w,c;}e[maxn<<1];

void add(int u,int v,int w,int c) {e[++tot]=(edge){v,head[u],w,c},head[u]=tot;}
void ins(int u,int v,int w,int c) {add(u,v,w,c),add(v,u,0,-c);}

int bfs() {
    memset(dis,63,4*(t+1));
    memset(vis,0,4*(t+1));
    queue<int > q;q.push(s);dis[s]=0,vis[s]=1;
    while(!q.empty()) {
        int now=q.front();q.pop(),vis[now]=0;
        for(int i=head[now];i;i=e[i].nxt)
            if(e[i].w>0&&dis[e[i].to]>dis[now]+e[i].c) {
                dis[e[i].to]=dis[now]+e[i].c;
                if(!vis[e[i].to]) vis[e[i].to]=1,q.push(e[i].to);
            }
    }return dis[t]<inf;
}
 
int dfs(int x,int f) {
    vis[x]=1;
    if(x==t) return cost+=f*dis[t],f;
    int used=0;
    for(int i=head[x];i;i=e[i].nxt)
        if((e[i].to==t||!vis[e[i].to])&&e[i].w>0&&dis[e[i].to]==dis[x]+e[i].c) {
            int d=dfs(e[i].to,min(f-used,e[i].w));
            if(d>0) e[i].w-=d,e[i^1].w+=d,used+=d;
            if(used==f) break;
        }return used;
}
 
int mcmf() {
    cost=0;while(bfs()) dfs(s,inf);return cost;
}
		
int main() {
	read(n),read(m);s=n+m+1,t=s+1;
	for(int i=1;i<=n;i++) read(a[i]),read(b[i]),read(C[i]),read(D[i]);
	for(int i=1,x,y;i<=m;i++) {
		read(x),read(y),l[x]++,l[y]++;b[x]++,b[y]++;
		ins(s,i+n,1,0),ins(i+n,x,1,0),ins(i+n,y,1,0);
	}
	int ans=0;
	for(int i=1;i<=n;i++) ans+=C[i]*sqr(a[i])+D[i]*sqr(b[i]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=l[i];j++) ins(i,t,1,C[i]+D[i]+2*C[i]*a[i]-2*D[i]*b[i]),a[i]++,b[i]--;
	write(ans+mcmf());
	return 0;
}