给每条路加上一个权值，每条路的费用是这条路的流量*权值，求最大流的最小费用。
每次spfa记录一下路径找最短的有流量的路，然后就是普通最大流的操作，反向边加流量什么的，网络流的作用依然是选择。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 #define LL long long 9 const int maxn=6100;10 int n,m,S,E;11 int wi[maxn]={},lo[maxn]={},c[maxn]={},d[maxn]={},zz[maxn]={};12 struct nod{13 int x,y,co,v,rev,next;14 }e[maxn*2];15 int head[maxn]={},vis[maxn]={},tot=0,mx;16 void init(int x,int y,int v,int co,int rev){17 e[++tot].x=x;e[tot].y=y;e[tot].co=co;18 e[tot].v=v;e[tot].rev=rev;e[tot].next=head[x];head[x]=tot;19 }20 queue q;21 int dis[maxn]={},fa[maxn]={};22 int spfa(){23 memset(vis,0,sizeof(vis));24 memset(dis,63,sizeof(dis));25 memset(fa,0,sizeof(fa));26 mx=dis[0];q.push(S);vis[S]=1;dis[S]=0;27 while(!q.empty()){28 int x=q.front();q.pop();vis[x]=0;29 for(int i=head[x];i;i=e[i].next){30 if(e[i].v){31 if(dis[e[i].y]>dis[x]+e[i].co){32 dis[e[i].y]=dis[x]+e[i].co;33 fa[e[i].y]=i;34 if(!vis[e[i].y]){35 vis[e[i].y]=1;q.push(e[i].y);36 }37 }38 }39 }40 }41 return fa[E];42 }43 int fyl(){44 int ans=0,val=mx;45 for(int i=fa[E];i;i=fa[e[i].x])val=min(val,e[i].v);46 for(int i=fa[E];i;i=fa[e[i].x]){47 e[i].v-=val;e[e[i].rev].v+=val;ans+=val*e[i].co;48 }49 return ans;50 }51 int main(){52 scanf("%d%d",&n,&m);S=n+m+1;E=S+1;53 for(int i=1;i<=n;i++) scanf("%d%d%d%d",&wi[i],&lo[i],&c[i],&d[i]);54 int x,y;55 for(int i=1;i<=m;i++){56 scanf("%d%d",&x,&y);57 lo[x]++;lo[y]++;zz[x]++;zz[y]++;58 init(S,n+i,1,0,tot+2);init(n+i,S,0,0,tot);59 init(n+i,x,1,0,tot+2);init(x,n+i,0,0,tot);60 init(n+i,y,1,0,tot+2);init(y,n+i,0,0,tot);61 }62 int ans=0;63 for(int i=1;i<=n;i++){64 ans+=wi[i]*wi[i]*c[i]+lo[i]*lo[i]*d[i];65 for(int j=1;j<=zz[i];j++){66 int z=c[i]*(2*wi[i]+1)-d[i]*(2*lo[i]-1);67 init(i,E,1,z,tot+2);init(E,i,0,-z,tot);68 wi[i]++;lo[i]--;69 }70 }71 while(spfa())ans+=fyl();72 printf("%d\n",ans);73 return 0;74 }