洛谷 P3705 [SDOI2017]新生舞会 题解【网络流】【分数规划】

作者: wjyyy 分类: 分数规划,图论,网络流,解题报告 发布时间: 2018-06-05 12:05

点击量:14

这个题是主要是考01分数规划和网络流建模。

题目描述

学校组织了一次新生舞会,Cathy作为经验丰富的老学姐,负责为同学们安排舞伴。

 

有n个男生和n个女生参加舞会,每一个男生和一个女生一起跳舞,互为舞伴。

 

Cathy收集了这些同学之间的关系,比如两个人之前认识没计算得出\(a_{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=\frac{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}\)。

 

输出格式:

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

输入输出样例

输入样例#1:
3
19 17 16
25 24 23
35 36 31
9 5 6
3 4 2
7 8 9
输出样例#1:
5.357143

说明

对于10%的数据, \(1\le n\le 5\)

 

对于40%的数据, \(1\le n\le 18\)

 

另有20%的数据, \(b_{i,j}\le 1\)

 

对于100%的数据, \(1\le n\le 100,1\le a_{i,j},b_{i,j}\le 10^4\)

   首先这个题需要匹配,而所有的男生和女生间都可以互相匹配,而每个男生只找一个女生,这就是二分图匹配,并且有\(n\)对和\(n^2\)条边。而要跑的是最佳匹配,就需要题目中所说的“C值最大”。

 

   C是由\(a_{i,j}\)和\(b_{i,j}\)确定的,因此我们要选择使C最大的n条边,这就是分数规划问题。

 

   分数规划问题是这样的,设一共有n个元素,每个元素可以选或不选,选择第i个元素会对分子加上\(a_i\),对分母加上\(b_i\)。这样就可以将这种状况抽象成一个模型:共取k个数,令\(L=\frac{\sum^{k}_{i=1}a_i}{\sum^{k}_{i=1}b_i}\),在不能确定k的情况下,这是不好预估的,那么我们将要选的元素,附加一个权值\(x_i\),如果选择这个元素,将\(x_i\)置1,不选置0。我们的L就会变成\(L=\frac{\sum^{n}_{i=1}a_i\times x_i}{\sum^{n}_{i=1}b_i\times x_i}\)。

 

   将上述式子变形,得到\(\sum^{n}_{i=1}a_i\times x_i =L\times \sum^{n}_{i=1}b_i\times x_i\),将L乘进去,得到\(\sum^{n}_{i=1}a_i\times x_i =\sum^{n}_{i=1}L\times b_i\times x_i\)。因此,如果\(f=\sum^{n}_{i=1}a_i\times x_i -\sum^{n}_{i=1}L\times b_i\times x_i>0\)那么L还有增加的余地,如果小于0,说明L不能满足这一条件,取不到而越界,L必须要减小。

 

   上述情况,我们可以用二分答案来缩小L的区间,上界是预估的极端情况。

 

   而一般最后的答案都是保留t位小数,我们只需要设置eps=1e-(t+1)即可。

 

   那么选一对男女生\((i,j)\),给\(f\)增加了\(a_{i,j}-L\times b{i,j}\)的代价,而我们在上面提到这里要找二分图完备最大权值匹配,这个模型就可以建出来了。

 

   和二分图匹配跑最大流一样,建出一个源点为0,汇点为\(t\notin[0,2n]\)的网络流,0和t连边的花费为0,其他花费为\(a_{i,j}-L\times b{i,j}\),每个男生和女生连接花费为\(a_{i,j}-L\times b{i,j}\)的边,所有边权值为1。因为是完备匹配,所以最大流一定是n。随着L的改变,图的权值也会改变,所以每次检验L时都要重新构图。

 

    如果最终\(f=\sum^{n}_{i=1}a_i\times x_i -\sum^{n}_{i=1}L\times b_i\times x_i\)的结果大于0,说明L还有增大的余地,将l置为mid,如果小于0,则不成立。

 

   值得注意的是,跑费用流的时候,一定要把所有spfa跑完,并且需要把dis的初始值设为\(-\infty \)不然是错的。。。

   还有,这个题是稠密图,因此邻接矩阵会比邻接表快。。。邻接表卡常很严重。。

 

Code:

#include<cstdio>
#include<cstring>
#include<deque>
using std::deque;
int v[205][205];
double w[205][205];

int t=201,n;//统一以t为汇点
int a[201][201],b[201][201];
int pre[220];
bool used[220];
double ans=0.0;
double dis[220];

bool spfa()
{
    dis[0]=0.0;
    for(int i=1;i<=201;i++)//需要赋值负无穷,不然不能更新。
        dis[i]=-1000000;
    pre[0]=0;
    memset(used,0,sizeof(used));
    deque<int> q;
    q.push_back(0);
    while(!q.empty())
    {
        int k=q.front();
        q.pop_front();
        used[k]=false;
        for(int i=1;i<=201;(i==2*n)?i=201:i++)
        {
            if(v[k][i]>0&&dis[i]<dis[k]+w[k][i])
            {
                dis[i]=dis[k]+w[k][i];
                pre[i]=k;
                if(!used[i])
                {
                    if(q.empty()||dis[i]<dis[k])//spfa玄学优化
                        q.push_front(i);
                    else
                        q.push_back(i);
                    used[i]=true;
                }
            }
        }
    }
    if(dis[201]==-1000000)//说明此次spfa找不到到t的最短路
        return false;
    return true;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=n+1;j<=2*n;j++)
            scanf("%d",&a[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=n+1;j<=2*n;j++)
            scanf("%d",&b[i][j]);
    double l=0.0,r=20000.0,mid;
    double eps=1e-7;//设置精度
    while(r-l>eps)//分数规划的二分
    {
        mid=(l+r)/2.0;

        for(int i=1;i<=n;i++)//初始化源点流出边
        {
            v[0][i]=1;
            w[0][i]=0.0;
            v[i][0]=0;
            w[i][0]=0.0;
        }
        for(int i=n+1;i<=2*n;i++)//初始化汇点流入边
        {
            v[i][201]=1;
            w[i][201]=0.0;
            v[201][i]=0;
            w[201][i]=0.0;
        }
        for(int i=1;i<=n;i++)
            for(int j=n+1;j<=2*n;j++)//建网络流
            {
                v[i][j]=1;
                w[i][j]=a[i][j]-mid*b[i][j];
                v[j][i]=0;
                w[j][i]=-(a[i][j]-mid*b[i][j]);//反边的费用也是反的
            }
        ans=0.0;
        while(spfa())//最大费用流
        {
            int p=201;
            while(p!=NULL)
            {
                v[pre[p]][p]--;
                v[p][pre[p]]++;
                p=pre[p];
            }
            ans+=dis[201];
        }
        if(ans>0)
            l=mid;
        else
            r=mid;
    }
    printf("%.6lf\n",l);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */