bzoj1449&&bzoj2895

题解：

S连每场比赛流量1费用0 
每场比赛连参赛队流量1费用0

我们发现调整一次 由win，lose变为 win+1，lose-1的费用为 
(C*(win+1)^2+D*(lose-1)^2) - (C*win^2+D*lose^2)=C*(2*win+1)-D*(2*lose-1) 
暴力连边就可以了 
最后的答案=最想费用流+最初假设所有队伍都输的收益

代码：

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int N=;

int S,W,lose[N],sum[N],win[N],ans,C[N],D[N];

int fi[N],n,t,cas,m,x,y,z,f[N],ne[N],num,zz[N],fl[N],gp[N],dist[N],pre[N],sl[N];

void jb(int x,int y,int z,int s)

{

    ne[num]=fi[x];

    fi[x]=num;

    zz[num]=y;

    sl[num]=z;

    fl[num++]=s;

    ne[num]=fi[y];

    fi[y]=num;

    zz[num]=x;

    sl[num]=;

    fl[num++]=-s;

}

int spfa()

{

    memset(dist,0x3f,sizeof dist);

    memset(pre,-,sizeof pre);

    memset(gp,,sizeof gp);

    memset(f,,sizeof f);

    queue<int > Q;

    Q.push(S);

    dist[S]=;

    while (!Q.empty())

     {

         int now=Q.front();

         Q.pop();

         f[now]=;

         for (int i=fi[now];i!=-;i=ne[i])

          if (sl[i]>)

           {

              int t=zz[i];

              if (dist[t]>dist[now]+fl[i])

               {

                   dist[t]=dist[now]+fl[i];

                   pre[t]=now;

                   gp[t]=i;

                   if (!f[t])

                    {

                        f[t]=;

                        Q.push(t);

                    }

               }

           }

     }

    if (pre[W]==-)return ;

    return ;

}

void Max_flow()

{

    int cost=,flow=;

    while (!spfa())

     {

         int f=1e9;

         for (int i=W;i!=S;i=pre[i])

          f=min(f,sl[gp[i]]);

         cost+=f;

        flow+=dist[W]*f;

        for (int i=W;i!=S;i=pre[i])

         {

             sl[gp[i]]-=f;

             sl[gp[i]^]+=f;

         }

     }

    printf("%d\n",flow+ans);

}

int main()

{

    memset(fi,-,sizeof fi);

    scanf("%d%d",&n,&m);

    S=n+m+,W=S+;

    for (int i=;i<=n;i++)scanf("%d%d%d%d",&win[i],&lose[i],&C[i],&D[i]);

    for (int i=;i<=m;i++)

     {

        int x,y;

        scanf("%d%d",&x,&y);

        jb(S,n+i,,);

        jb(n+i,x,,);

        jb(n+i,y,,);

        sum[x]++,sum[y]++;

     }

    for (int i=;i<=n;i++)lose[i]+=sum[i];

    for (int i=;i<=n;i++)ans+=C[i]*win[i]*win[i]+D[i]*lose[i]*lose[i];

    for (int i=;i<=n;i++)

     for (int j=;j<=sum[i];j++)

      {

        jb(i,W,,C[i]*(*win[i]+)-D[i]*(*lose[i]-));

        win[i]++;lose[i]--;

      }

    Max_flow();

}