bzoj 1449: [JSOI2009]球队收益 凸费用拆边费用流 由于有负边，先spfa处理顶标然后zkw

/**************************************************************
    Problem: 1449
    User: wangyucheng
    Language: C++
    Result: Accepted
    Time:268 ms
    Memory:2532 kb
****************************************************************/
 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define maxn 6200
#define maxm 52000
#define inf 0x3fffffff
#define v(i) w[i].v 
#define c(i) w[i].c
#define u(i) w[i].u
struct P{
  int v,c,u;    
}w[maxm];
int e[maxm],ne[maxm];
int nn=1;
void add(int x,int y,int cc,int uu){
  ne[++nn]=e[x],e[x]=nn,v(nn)=y,c(nn)=cc,u(nn)=uu;  
}
int v[maxn];
int s[maxn];
int n,m,win[maxn],lose[maxn],c[maxn],d[maxn],dist[maxn];
int S,T;
int a[maxn],b[maxn],been[maxn];
void spfa(){
    for(int i=1;i<T;i++)dist[i]=inf;
    queue<int> jj;
    jj.push(T);
    dist[T]=0;
    while(!jj.empty()){
      int x=jj.front();
      jj.pop();
      been[x]=0;
      for(int i=e[x];i;i=ne[i])if(dist[v(i)]>dist[x]+c(i)&&u(i)){
            dist[v(i)]=dist[x]+c(i);
            if(!been[v(i)])been[v(i)]=1,jj.push(v(i));
      } 
    }
}
int ans;
int ff;
int zeng(int no,int mm){
  if(no==T)return ans+=dist[S]*mm,mm;
  int r=mm,k;
  v[no]=ff;
  for(int i=e[no];i&&r;i=ne[i])if(ff!=v[v(i)]&&u(i)&&dist[no]==dist[v(i)]+c(i)){
     k=zeng(v(i),min(r,u(i)));
     u(i)-=k;
     u(i^1)+=k;
     r-=k;  
  } 
  return mm-r;
}
bool modlab(){
   int minn=inf;
   for(int i=1;i<=T;i++)if(ff==v[i]){
        for(int j=e[i];j;j=ne[j])if(ff!=v[v(j)]&&u(j))minn=min(minn,dist[v(j)]+c(j)-dist[i]);
    }
    if(minn==inf)return 0;
    for(int i=1;i<=T;i++)if(ff==v[i])dist[i]+=minn;
    return 1;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d%d",&win[i],&lose[i],&c[i],&d[i]);
    }
    for(int i=1;i<=m;i++){
      scanf("%d%d",&a[i],&b[i]);
      s[a[i]]++,s[b[i]]++;
    }
    S=n+m+1;
    T=S+1;  
    for(int i=1;i<=n;i++){
      ans+=win[i]*win[i]*c[i]+d[i]*(s[i]+lose[i])*(lose[i]+s[i]);
      int op=2*(-lose[i]-s[i])*d[i]+2*c[i]*win[i];
       for(int j=1;j<=s[i];j++)add(i,T,op+(2*j-1)*(c[i]+d[i]),1),add(T,i,-op-(2*j-1)*(c[i]+d[i]),0);   
    }
    for(int i=1;i<=m;i++){
      add(S,i+n,0,1);
      add(i+n,S,0,0);
      add(i+n,a[i],0,1);
      add(a[i],i+n,0,0);
      add(i+n,b[i],0,1);
      add(b[i],i+n,0,0);    
    }
    spfa();
    do do ff++;
    while(zeng(S,inf));
    while(modlab());
    cout<<ans;
}