BZOJ 1449: [JSOI2009]球队收益 最小费用最大流 网络流

https://www.lydsy.com/JudgeOnline/problem.php?id=1449

给每条路加上一个权值，每条路的费用是这条路的流量*权值，求最大流的最小费用。

每次spfa记录一下路径找最短的有流量的路，然后就是普通最大流的操作，反向边加流量什么的，网络流的作用依然是选择。

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<queue>

 using namespace std;

 #define LL long long

 const int maxn=;

 int n,m,S,E;

 int wi[maxn]={},lo[maxn]={},c[maxn]={},d[maxn]={},zz[maxn]={};

 struct nod{

     int x,y,co,v,rev,next;

 }e[maxn*];

 int head[maxn]={},vis[maxn]={},tot=,mx;

 void init(int x,int y,int v,int co,int rev){

     e[++tot].x=x;e[tot].y=y;e[tot].co=co;

     e[tot].v=v;e[tot].rev=rev;e[tot].next=head[x];head[x]=tot;

 }

 queue<int>q;

 int dis[maxn]={},fa[maxn]={};

 int spfa(){

     memset(vis,,sizeof(vis));

     memset(dis,,sizeof(dis));

     memset(fa,,sizeof(fa));

     mx=dis[];q.push(S);vis[S]=;dis[S]=;

     while(!q.empty()){

         int x=q.front();q.pop();vis[x]=;

         for(int i=head[x];i;i=e[i].next){

             if(e[i].v){

                 if(dis[e[i].y]>dis[x]+e[i].co){

                     dis[e[i].y]=dis[x]+e[i].co;

                     fa[e[i].y]=i;

                     if(!vis[e[i].y]){

                         vis[e[i].y]=;q.push(e[i].y);

                     }

                 }

             }

         }

     }

     return fa[E];

 }

 int fyl(){

     int ans=,val=mx;

     for(int i=fa[E];i;i=fa[e[i].x])val=min(val,e[i].v);

     for(int i=fa[E];i;i=fa[e[i].x]){

         e[i].v-=val;e[e[i].rev].v+=val;ans+=val*e[i].co;

     }

     return ans;

 }

 int main(){

     scanf("%d%d",&n,&m);S=n+m+;E=S+;

     for(int i=;i<=n;i++) scanf("%d%d%d%d",&wi[i],&lo[i],&c[i],&d[i]);

     int x,y;

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

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

         lo[x]++;lo[y]++;zz[x]++;zz[y]++;

         init(S,n+i,,,tot+);init(n+i,S,,,tot);

         init(n+i,x,,,tot+);init(x,n+i,,,tot);

         init(n+i,y,,,tot+);init(y,n+i,,,tot);

     }

     int ans=;

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

         ans+=wi[i]*wi[i]*c[i]+lo[i]*lo[i]*d[i];

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

             int z=c[i]*(*wi[i]+)-d[i]*(*lo[i]-);

             init(i,E,,z,tot+);init(E,i,,-z,tot);

             wi[i]++;lo[i]--;

         }

     }

     while(spfa())ans+=fyl();

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

     return ;

 }