【题意】
【分析】
这道题目可以说集结了蛮多套路
首先就是平方拆边，平方拆边指的是当贡献是平方这种形式的时候，我们可以增量构造边，保证每次走的边递增
比如$(a+1)^2-a^2=2a+1$，那么我们建的边就是a,3a,5a.....，这样既保证了从小到大依次走，也保证了平方的形式
第二个套路就是费用提前计算，我们可以先假设所有的球队都输了所有比赛，然后把赢一场比赛的贡献变成赢得-输的即可
【代码】
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define mp make_pair #define fi firstP #define se second const int maxn=10005; const int maxm=10005; int n,m,head[maxn]; struct edge { int to,nxt,v,c; }e[maxm<<1]; int tot=1,S,T; void add(int x,int y,int z,int c) { e[++tot].to=y; e[tot].nxt=head[x]; e[tot].v=z; e[tot].c=c; head[x]=tot; e[++tot].to=x; e[tot].nxt=head[y]; e[tot].v=0; e[tot].c=-c; head[y]=tot; } const int inf=0x3f3f3f3f; int dis[maxn],vis[maxn],pre[maxn]; bool spfa() { for(int i=S;i<=T;i++) vis[i]=0,dis[i]=inf; dis[S]=0; queue <int> q; q.push(S); vis[S]=1; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i;i=e[i].nxt) { int to=e[i].to; if(dis[to]>dis[u]+e[i].c && e[i].v) { dis[to]=dis[u]+e[i].c; pre[to]=i; if(!vis[to]) { q.push(to); vis[to]=1; } } } vis[u]=0; } return (dis[T]!=inf); } int mcmf() { int res=0,cost=0; while(spfa()) { int flow=inf; for(int i=T;i!=S;i=e[pre[i]^1].to) flow=min(flow,e[pre[i]].v); for(int i=T;i!=S;i=e[pre[i]^1].to) { e[pre[i]].v-=flow; e[pre[i]^1].v+=flow; cost+=e[pre[i]].c*flow; } } return cost; } int a[maxn],b[maxn],c[maxn],d[maxn],win[maxn]; int main() { scanf("%d%d",&n,&m); S=0; T=n+m+1; int x,y; for(int i=1;i<=n;i++) scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]); for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); win[x]++; win[y]++; b[x]++; b[y]++; add(i+n,x,1,0); add(i+n,y,1,0); add(S,i+n,1,0); } int precost=0; for(int i=1;i<=n;i++) precost+=c[i]*a[i]*a[i]+d[i]*b[i]*b[i]; for(int i=1;i<=n;i++) for(int j=1;j<=win[i];j++) { add(i,T,1,c[i]+d[i]+2*c[i]*a[i]-2*d[i]*b[i]); a[i]++; b[i]--; } printf("%d",precost+mcmf()); return 0; }