Description Input Output 一个整数表示联盟里所有球队收益之和的最小值。
首先假设全输，然后给每场比赛分配一个赢家，每个队伍每多赢一场多获得的收益作为费用。
但是有一个问题，如何保证每次走的是对应的边？也就是，如何保证赢第一场的时候增加的收益是赢一场减赢零场，而不是赢两场减赢一场？可以发现，假设当前赢了 x 场输了
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int s=6005,t=6006,oo=0x3f3f3f3f,mod=6007;
int fir[6010],ne[200010],to[200010],w[200010],c[200010],
que[6010],in[6010],minw[6010],len[6010],fa[6010],
cnt[5010],ci[5010],di[5010],win[5010],lose[5010],
n,m,num,ans;
void add(int u,int v,int x,int y)
{num++;ne[num*2]=fir[u];fir[u]=num*2;to[num*2]=v;w[num*2]=x;c[num*2]=y;ne[num*2+1]=fir[v];fir[v]=num*2+1;to[num*2+1]=u;w[num*2+1]=0;c[num*2+1]=-y;
}
int main()
{int hd,tl,u,v;scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%d%d%d%d",&win[i],&lose[i],&ci[i],&di[i]);for (int i=1;i<=m;i++){scanf("%d%d",&u,&v);cnt[u]++;cnt[v]++;add(s,i+n,1,0);add(i+n,u,1,0);add(i+n,v,1,0);}for (int i=1;i<=n;i++)for (int j=1;j<=cnt[i];j++)add(i,t,1,ci[i]*(win[i]+j)*(win[i]+j)+di[i]*(lose[i]+cnt[i]-j)*(lose[i]+cnt[i]-j)-ci[i]*(win[i]+j-1)*(win[i]+j-1)-di[i]*(lose[i]+cnt[i]-j+1)*(lose[i]+cnt[i]-j+1));for (int i=1;i<=n;i++) ans+=ci[i]*win[i]*win[i]+di[i]*(lose[i]+cnt[i])*(lose[i]+cnt[i]);while (1){hd=0,tl=1;que[0]=s;in[s]=1;memset(minw,0,sizeof(minw));minw[s]=oo;memset(len,0x3f,sizeof(len));len[s]=0;while (hd!=tl){u=que[hd++];hd%=mod;for (int i=fir[u];i;i=ne[i])if (w[i]&&len[v=to[i]]>len[u]+c[i]){len[v]=len[u]+c[i];minw[v]=min(minw[u],w[i]);fa[v]=i;if (!in[v]){in[v]=1;que[tl++]=v;tl%=mod;}}in[u]=0;}if (!minw[t]) break;ans+=minw[t]*len[t];for (int i=fa[t];i;i=fa[to[i^1]]){w[i]-=minw[t];w[i^1]+=minw[t];}}printf("%d\n",ans);
}