1449: [JSOI2009]球队收益
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 1124 Solved: 635
[Submit][Status][Discuss]
Description
Input
Output
一个整数表示联盟里所有球队收益之和的最小值。
Sample Input
3 3
1 0 2 1
1 1 10 1
0 1 3 3
1 2
2 3
3 1
1 0 2 1
1 1 10 1
0 1 3 3
1 2
2 3
3 1
Sample Output
43
HINT
Source
二次费用流模板题。
我们先假设每个队剩下的比赛都输，然后用费用流来让每次比赛的两队之一获胜。
考虑从S向每个比赛连一条容量为1的边，从每个比赛向另两个球队也连容量为1 的边。
注意上述边都是没有边权的。
那么考虑一个球队多赢一场的影响？
derta[x] = C*(2*win[x]+1) - D*(2*lose[x]-1) ，其中win是输入的，lose为输入的加上之后这个队的比赛数。
发现随着一个队赢的次数增多，这个derta会越来越大，而我们费用流是优先走小的边，正好符合先后顺序。
所以最小费用最大流的情况一定符合最优解。
#include<bits/stdc++.h>#define ll long long#define maxn 30005#define pb push_backusing namespace std;const int inf=1<<30;struct lines{int from,to,flow,cap,cost;}l[maxn*10];ll tot=0;vector<int> g[maxn];int S,T,t=-1,d[maxn];int a[maxn],p[maxn];bool iq[maxn];inline void add(int from,int to,int cap,int cost){l[++t]=(lines){from,to,0,cap,cost},g[from].pb(t);l[++t]=(lines){to,from,0,0,-cost},g[to].pb(t);}inline bool BFS(){queue<int> q;memset(d,0x3f,sizeof(d));d[S]=0,p[S]=0,a[S]=inf;iq[S]=1,q.push(S);int x; lines e;while(!q.empty()){x=q.front(),q.pop();for(int i=g[x].size()-1;i>=0;i--){e=l[g[x][i]];if(e.flow<e.cap&&d[x]+e.cost<d[e.to]){d[e.to]=d[x]+e.cost;a[e.to]=min(a[x],e.cap-e.flow);p[e.to]=g[x][i];if(!iq[e.to]) iq[e.to]=1,q.push(e.to); }}iq[x]=0;}if(d[T]==d[T+1]) return 0;tot+=a[T]*(ll)d[T];int now=T,pre;while(now!=S){pre=p[now];l[pre].flow+=a[T];l[pre^1].flow-=a[T];now=l[pre].from;}return 1;}int n,m,C[5005],D[5005];int win[5005],lose[5005];int cnt=0,X[1005],Y[1005];inline int sq(int x){return x*x;}inline void MFMC(){while(BFS());}inline void build(){for(int i=1;i<=n;i++){tot+=C[i]*sq(win[i])+D[i]*sq(lose[i]);}for(int i=1;i<=m;i++){add(S,i+n,1,0);add(i+n,X[i],1,0);add(i+n,Y[i],1,0);add(X[i],T,1,-D[X[i]]*(2*lose[X[i]]-1)+C[X[i]]*(2*win[X[i]]+1));win[X[i]]++,lose[X[i]]--;add(Y[i],T,1,-D[Y[i]]*(2*lose[Y[i]]-1)+C[Y[i]]*(2*win[Y[i]]+1));win[Y[i]]++,lose[Y[i]]--;}}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);}S=0,T=m+n+1;for(int i=1;i<=m;i++){scanf("%d%d",X+i,Y+i);lose[X[i]]++,lose[Y[i]]++;}build();MFMC();printf("%lld\n",tot);return 0;}
[JSOI2009]球队收益
原文地址：https://www.cnblogs.com/JYYHH/p/8536425.html