bzoj1149/2895 [JSOI2009]球队收益

bzoj1149/2895 [JSOI2009]球队收益

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

这是一道非常标准的两倍经验题.. 但是2895是权限题.. 为什么呐看图

这就是权限狗的不同啊！连数据都强一点..

借这道题我也学了下zkw费用流.. 也是不错哒..

这真的是一道好题..

一开始我想的是比赛一堆点、球队一堆点，然后当题目给出比赛的两支球队时我先随便假设某一方赢，然后用费用流来反悔..
答案求的是平方的.. 那就拆边咯

但是想了一会这样做还是不对.. 因为每次你的反悔都会涉及到两支球队，一条费用流是不能同时算到两支球队的结果（自己好好想想为什么..）

那么既然不能算两支球队，能不能找到一种构图方法只需要跟一支球队有关呢？

这样的话我们就可以想到一种做法.. 先把比赛的双方都判负.. 那么我只需要用费用流来跑某场比赛是哪一支球队获胜.. 既然只涉及到一支球队，计算答案就方便很多了..

对于第$i$支球队来说，每把一个输的变成赢得的增加的收益为：
$AddProfit=C_i[(win_i+k)^2-(win_i+k-1)^2]+D_i[(lose_i-k)^2-(lose_i-k+1)^2]$
其中$k$表示当前已经把$k-1$个输变成赢，现在改变第$k$个
化简该公式：
$AddProfit=C_i(2win_i+2k-1)+D_i(-2lose_i+2k-1)$

那么拆下边.. 跑个费用流就好啦..

同样的，我们一开始把比赛双方都判胜也行..

code

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;
const int Maxn = 11000;
struct node {int x, y, next, c, d, opp;
}a[Maxn*10]; int first[Maxn], len;
int _min ( int x, int y ){ return x < y ? x : y; }
void ins ( int x, int y, int c, int d ){len ++; int k1 = len;a[len].x = x; a[len].y = y; a[len].c = c; a[len].d = d;a[len].next = first[x]; first[x] = len;len ++; int k2 = len;a[len].x = y; a[len].y = x; a[len].c = 0; a[len].d = -d;a[len].next = first[y]; first[y] = len;a[k1].opp = k2;a[k2].opp = k1;
}
int st, ed;
int mark[Maxn];
int n, m, ans;
int win[Maxn], lose[Maxn], C[Maxn], D[Maxn];
int de[Maxn];
int dis[Maxn], pre[Maxn];
bool bfs (){queue <int> q;memset ( mark, 0, sizeof (mark) );memset ( dis, 63, sizeof (dis) );memset ( pre, -1, sizeof (pre) );q.push (st); mark[st] = 1; dis[st] = 0;while ( !q.empty () ){int x = q.front (); q.pop ();for ( int k = first[x]; k; k = a[k].next ){int y = a[k].y;if ( dis[y] > dis[x]+a[k].d && a[k].c > 0 ){dis[y] = dis[x]+a[k].d;pre[y] = k;if ( mark[y] == false ){mark[y] = true;q.push (y);}}}mark[x] = false;}return pre[ed] > 0;
}
int dfs ( int x, int flow ){mark[x] = 1;if ( x == ed ) return flow;int delta = 0;for ( int k = first[x]; k; k = a[k].next ){int y = a[k].y;if ( dis[y] == dis[x]+a[k].d && a[k].c > 0 && flow-delta > 0 && !mark[y] ){int minf = dfs ( y, _min ( a[k].c, flow-delta ) );ans += minf*a[k].d;delta += minf;a[k].c -= minf;a[a[k].opp].c += minf;}}return delta;
}
int main (){int i, j, k;scanf ( "%d%d", &n, &m );for ( i = 1; i <= n; i ++ ){scanf ( "%d%d%d%d", &win[i], &lose[i], &C[i], &D[i] );}memset ( de, 0, sizeof (de) );len = 0; memset ( first, 0, sizeof (first) );st = 0; ed = n+m+1;for ( i = 1; i <= m; i ++ ){int x, y;scanf ( "%d%d", &x, &y );de[x] ++; de[y] ++;lose[x] ++; lose[y] ++;ins ( i, x+m, 1, 0 );ins ( i, y+m, 1, 0 );}int sum = 0;for ( i = 1; i <= n; i ++ ) sum += win[i]*win[i]*C[i] + lose[i]*lose[i]*D[i];for ( i = 1; i <= m; i ++ ) ins ( st, i, 1, 0 );for ( i = 1; i <= n; i ++ ){for ( k = 1; k <= de[i]; k ++ ){ins ( i+m, ed, 1, C[i]*(2*win[i]+2*k-1)+D[i]*(-2*lose[i]+2*k-1) );}}ans = 0;while ( bfs () ){mark[ed] = 1;while (mark[ed]){memset ( mark, 0, sizeof (mark) );dfs ( st, 0x7fffffff );}}printf ( "%d\n", sum+ans );return 0;
}

看看这构图.. 这真的是一道好题啊..