bzoj 1449:[JSOI 2009]チーム収益(費用フロー)

タイトルの説明
トランスファゲート
バスケットボールのリーグ戦では、nチームがあり、チームの支出は彼らの勝負と関係があり、具体的には、iチーム目のシーズン総支出はCi∗x 2+Di∗y 2,Di<=Ciである.このうちx,yはそれぞれこのチームの今シーズンの勝負を示している.今シーズンは半分まで行われ、各チームはそれぞれwin[i]勝とlost[i]敗を収めた.そして次はm試合が行われる.リーグチームの最小総支出はいくらですか.
問題解
各チームについて、dui試合があると計算し、最初はすべてのチームの試合状態が負けていると仮定しました.すなわち、win[i]=win[i]、lost[i]=lost[i]+du[i]です.そして、勝つたびに総支出に与える影響を考えます.c[i](win[i]+1)2−c[i]win[i]2+d[i]∗(lost[i]−1)2−d[i]∗lost[i]2を簡略化してc[i]+d[i]+2∗win[i]∗c[i]−2∗lost[i]∗d[i]各チームにとって、どれだけの試合が残っているか、このチームが代表する点から合流点までいくつかの辺が連なり、各辺の容量は1で、費用は上式の容量は上式の答えは、エッジを1つ接続するたびにwin[i]++,lost[i]−−−,エッジウェイトを再計算します.試合ごとに必ず1チームが優勝し、すべてのソースポイントは試合ごとに代表のポイントに接続され、容量は1で、費用は0試合ごとに行われる2チームに接続され、容量は1で、費用は0である.それから料金の流れを走ればいいです.最後の答えには、初期値Σni=1 lost[i]∗lost[i]∗d[i]+win[i]∗win[i]∗c[i]を加えます.
コード#コード#

#include
#include
#include
#include
#include
#include
#define N 300010
#define inf 1000000000
using namespace std;
int n,tot,c[N],d[N],cost[N],remain[N],point[N],nxt[N],v[N],ctx[N];
int cty[N],du[N],dx[N],dy[N],dis[N],can[N],last[N],ans,m,lost[N],win[N],S,T,cnt[N];
void add(int x,int y,int z,int k)
{
    tot++; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; remain[tot]=z; cost[tot]=k;
    tot++; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; remain[tot]=0; cost[tot]=-k;
}
int addflow(int s,int t)
{
    int now=t; int ans=inf;
    while (now!=s) {
        ans=min(ans,remain[last[now]]);
        now=v[last[now]^1];
    }
    now=t;
    while (now!=s){
        remain[last[now]]-=ans;
        remain[last[now]^1]+=ans;
        now=v[last[now]^1];
    }
    return ans;
}
bool spfa(int s,int t)
{
    for (int i=1;i<=t;i++) dis[i]=inf,can[i]=0;
    queue<int> p; p.push(s); dis[s]=0; can[s]=1;
    while (!p.empty()){
        int now=p.front(); p.pop();
        for (int i=point[now];i!=-1;i=nxt[i])
         if (remain[i]&&dis[v[i]]>dis[now]+cost[i]){
            dis[v[i]]=dis[now]+cost[i];
            last[v[i]]=i;
            if(!can[v[i]]) {
                can[v[i]]=1;
                p.push(v[i]);
             }
         }
        can[now]=0;
    }
    if (dis[t]==inf) return false; 
    int flow=addflow(s,t);
    ans+=flow*dis[t];
    return true;
}
void solve(int s,int t)
{
    while(spfa(s,t));
}
int main()
{
    freopen("a.in","r",stdin);
//  freopen("my.out","w",stdout);
    scanf("%d%d",&n,&m);
    tot=-1;
    memset(point,-1,sizeof(point));
    for (int i=1;i<=n;i++) scanf("%d%d%d%d",&win[i],&lost[i],&c[i],&d[i]);
    S=n+m+1; T=S+1;
    for (int i=1;i<=m;i++) {
        int x,y; scanf("%d%d",&x,&y);
        add(S,i,1,0); dx[i]=x; dy[i]=y;
        du[x]++; du[y]++;
        add(i,x+m,1,0); ctx[i]=tot;
        add(i,y+m,1,0); cty[i]=tot; 
    }
    for (int i=1;i<=n;i++) lost[i]+=du[i];
    for (int i=1;i<=n;i++) ans+=c[i]*win[i]*win[i]+d[i]*lost[i]*lost[i];
    for (int i=1;i<=n;i++) 
     for (int j=1;j<=du[i];j++){
      int t=win[i]*2*c[i]+c[i]+d[i]-lost[i]*2*d[i];
      add(i+m,T,1,t);
      win[i]++; lost[i]--;
    }
    solve(S,T); 
    printf("%d
",ans);
}