首页 > 代码库 > 【bzoj4819】[Sdoi2017]新生舞会 分数规划+费用流

【bzoj4819】[Sdoi2017]新生舞会 分数规划+费用流

题目描述

 

学校组织了一次新生舞会,Cathy作为经验丰富的老学姐,负责为同学们安排舞伴。有n个男生和n个女生参加舞会买一个男生和一个女生一起跳舞,互为舞伴。Cathy收集了这些同学之间的关系,比如两个人之前认识没计算得出 a[i][j] ,表示第i个男生和第j个女生一起跳舞时他们的喜悦程度。Cathy还需要考虑两个人一起跳舞是否方便,比如身高体重差别会不会太大,计算得出 b[i][j],表示第i个男生和第j个女生一起跳舞时的不协调程度。当然,还需要考虑很多其他问题。Cathy想先用一个程序通过a[i][j]和b[i][j]求出一种方案,再手动对方案进行微调。Cathy找到你,希望你帮她写那个程序。一个方案中有n对舞伴,假设没对舞伴的喜悦程度分别是a‘1,a‘2,...,a‘n,假设每对舞伴的不协调程度分别是b‘1,b‘2,...,b‘n。令C=(a‘1+a‘2+...+a‘n)/(b‘1+b‘2+...+b‘n),Cathy希望C值最大。

 

输入

 

第一行一个整数n。
接下来n行,每行n个整数,第i行第j个数表示a[i][j]。
接下来n行,每行n个整数,第i行第j个数表示b[i][j]。
1<=n<=100,1<=a[i][j],b[i][j]<=10^4

 

输出

 

一行一个数,表示C的最大值。四舍五入保留6位小数,选手输出的小数需要与标准输出相等

 

样例输入

3
19 17 16
25 24 23
35 36 31
9 5 6
3 4 2
7 8 9

样例输出

5.357143


题解

分数规划+费用流

二分答案mid,将每个点的值看作a-b*mid。

由于每个男生只能搭配一名不同的女生,所以问题可以转化为:1个n*n的矩阵中每个位置都有1个数,求选出n个彼此不在同一行或同一列的数的和的最大值是多少。

加边s->i(1,0),i+n->t(1,0),i->j+n(1,v[i][j]),跑最大费用最大流,若大于0则调整下界,否则调整上界,直至上下界基本重合。

证明:如果最大费用大于0,则∑(v[ik][jk])>0,即∑(a[ik][jk]-b[ik][jk]*mid)>0,即∑a[ik][jk]>∑b[ik][jk]*mid,即∑a[ik][jk]/∑b[ik][jk]>mid,故需要调整下界来进一步更新答案,否则调整上界来调整答案。

#include <cstdio>#include <cstring>#include <queue>#define eps 1e-7using namespace std;queue<int> q;int n , head[210] , to[30000] , val[30000] , next[30000] , cnt , s , t , from[210] , pre[210];double a[110][110] , b[110][110] , cost[30000] , dis[210];void add(int x , int y , int v , double c){    to[++cnt] = y , val[cnt] = v , cost[cnt] = c , next[cnt] = head[x] , head[x] = cnt;    to[++cnt] = x , val[cnt] = 0 , cost[cnt] = -c , next[cnt] = head[y] , head[y] = cnt;}bool spfa(){    int x , i;    for(i = s ; i <= t ; i ++ ) from[i] = -1 , dis[i] = 10000000.0;    dis[s] = 0 , q.push(s);    while(!q.empty())    {        x = q.front() , q.pop();        for(i = head[x] ; i ; i = next[i])            if(val[i] && dis[to[i]] > dis[x] + cost[i])                dis[to[i]] = dis[x] + cost[i] , from[to[i]] = x , pre[to[i]] = i , q.push(to[i]);    }    return ~from[t];}double mincost(){    int k , i;    double ans = 0;    while(spfa())    {        k = 0x3f3f3f3f;        for(i = t ; i != s ; i = from[i]) k = min(k , val[pre[i]]);        ans += k * dis[t];        for(i = t ; i != s ; i = from[i]) val[pre[i]] -= k , val[pre[i] ^ 1] += k;    }    return ans;}bool judge(double mid){    int i , j;    memset(head , 0 , sizeof(head));    cnt = 1;    for(i = 1 ; i <= n ; i ++ ) add(s , i , 1 , 0);    for(i = 1 ; i <= n ; i ++ ) add(i + n , t , 1 , 0);    for(i = 1 ; i <= n ; i ++ )        for(j = 1 ; j <= n ; j ++ )            add(i , j + n , 1 , mid * b[i][j] - a[i][j]);    return mincost() < 0;}int main(){    int i , j;    double l = 0.0 , r = 10000000.0 , mid;    scanf("%d" , &n);    s = 0 , t = 2 * n + 1;    for(i = 1 ; i <= n ; i ++ ) for(j = 1 ; j <= n ; j ++ ) scanf("%lf" , &a[i][j]);    for(i = 1 ; i <= n ; i ++ ) for(j = 1 ; j <= n ; j ++ ) scanf("%lf" , &b[i][j]);    while(l <= r)    {        mid = (l + r) / 2;        if(judge(mid)) l = mid + eps;        else r = mid - eps;    }    printf("%.6lf\n" , (l + r) / 2);    return 0;}

 

【bzoj4819】[Sdoi2017]新生舞会 分数规划+费用流