https://www.lydsy.com/JudgeOnline/problem.php?id=1449
给每条路加上一个权值，每条路的费用是这条路的流量*权值，求最大流的最小费用。
每次spfa记录一下路径找最短的有流量的路，然后就是普通最大流的操作，反向边加流量什么的，网络流的作用依然是选择。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 #include<queue> 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<int>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 ",ans); 73 return 0; 74 }