1449: [JSOI2009] 球队收益
- Time Limit: 5 Sec Memory Limit: 64 MB
- Submit: 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
- 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_back
- using 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;
- }
来源: http://www.bubuko.com/infodetail-2521622.html