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_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;
}