[bzoj1449/2895]-[JSOI2009]球队收益

题目（BZOJ）
题目（洛谷）
 
这题主要是建模比较巧，如果你做过bzoj2597那么这题应该很好做。
（顺便吐槽一下bzoj2597，居然卡常！）
首先，假设每场比赛每个人都输，计算出初始答案，
之后考虑每一场比赛：不难发现一场比赛只能有一个人赢，我们可以抽象地认为这场比赛 $i$ 赢的话就是该比赛向 $i$ 提供了 $1$ 的流量。
同时还发现，一个队的输赢是不影响其他队伍的，并且我们一开始假设每场比赛每个队都输，也就是说我们要决定哪些队伍赢。从输到赢会增加一定费用，所以对于第 $i$ 支队伍，向汇点 $T$ 连 $x$ 条弧（$x$ 代表该队伍最多赢的场数），容量为 $1$，费用为 $2*C_i*win_i+C_i+D_i-2*D_i*lose_i$，并且每次加弧长时，$win_i++$，$lose_i--$。
最后跑一次费用流，完毕。

#include <cstdio>
#include <cstring>
#include <climits>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#define ll long long
using namespace std;
template <class _E> inline void read(_E &e){
    e=0;bool ck=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
    while(isdigit(ch)){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
    if(ck)e=-e;
}
const int M=7050;
const int N=5050;
const int INF=0x3f3f3f3f;
int n,m,S,T;
int win[N],lose[N],in[N],C[N],D[N],cost;
struct Edge{
    int u,v,cap,flow,cost;
};
vector <Edge> edges;
vector <int> g[M];
int q[M],a[M],d[M],p[M],L,R;bool inq[M];
inline void ad(int u,int v,int cap,int cost){
    edges.push_back((Edge){u,v,cap,0,cost});
    edges.push_back((Edge){v,u,0,0,-cost});
    int sz=edges.size();
    g[u].push_back(sz-2);g[v].push_back(sz-1);
}
inline bool spfa(int s,int t,int &flow,int &cost){
    L=1,R=0;q[++R]=s;
    memset(d,INF,sizeof d);
    a[s]=INF;d[s]=0;p[s]=0;inq[s]=1;
    while(L<=R){
        int u=q[L];L++;inq[u]=0;
        for(int i=0;i<g[u].size();++i){
            Edge &e=edges[g[u][i]];int v=e.v;
            if(e.cap>e.flow&&d[v]>d[u]+e.cost){
                d[v]=d[u]+e.cost;
                p[v]=g[u][i];
                a[v]=min(a[u],e.cap-e.flow);
                if(!inq[v])q[++R]=v,inq[v]=1;
            }
        }
    }
    if(d[t]==INF)return false;
    flow+=a[t];cost+=a[t]*d[t];
    int u=t;
    while(u!=s){
        edges[p[u]].flow+=a[t];
        edges[p[u]^1].flow-=a[t];
        u=edges[p[u]].u;
    }
    return true;
}
inline int mincost(int s,int t){
    int flow=0,cost=0;
    while(spfa(s,t,flow,cost));
    return cost;
}
int main(){
    read(n),read(m);S=n+m+1;T=S+1;
    for(int i=1;i<=n;++i){
        read(win[i]);read(lose[i]);
        read(C[i]);read(D[i]);
    }
    for(int i=1;i<=m;++i){
        int x,y;read(x),read(y);
        ad(S,i,1,0);
        ad(i,x+m,1,0);ad(i,y+m,1,0);
        in[x]++;in[y]++;
    }
    for(int i=1;i<=n;++i)lose[i]+=in[i];
    for(int i=1;i<=n;++i)cost+=win[i]*win[i]*C[i]+lose[i]*lose[i]*D[i];
    for(int i=1;i<=n;++i){
        for(int j=1;j<=in[i];++j){
            ad(i+m,T,1,2*C[i]*win[i]+C[i]+D[i]-2*D[i]*lose[i]);
            win[i]++;lose[i]--;
        }
    }
    cost+=mincost(S,T);
    printf(
    return 0;
}