洛谷 P3705 [SDOI2017]新生舞会 解题报告

时间：2021-12-22 06:55:19

P3705 [SDOI2017]新生舞会

题目描述

学校组织了一次新生舞会，\(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位小数，选手输出的小数需要与标准输出相等。

说明

对于10%的数据， \(1≤n≤5\)

对于40%的数据， \(1≤n≤18\)

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

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

做的第一道01分数规划的题。

01分数规划问题大多采用一种二分答案解法。

我们分数拆成整数，即

\(C*(b'_1+b'_2+...+b'_n)=a'_1+a'_2+...+a'_n\)

然后猜测一个\(C\)的值，检验在最优\(a,b\)配对的情况下左边与右边的大小关系，进而对\(C\)进行二分答案

如何求解最优配对呢？

再转化一下式子，左边-右边=

\(\sum_{i=1}^n (a'_i-b'_i*C)\)

我们要求解sum的最大值。

如果我们把对应点连上边\((a'_i-b'_i*C)\)，就变成了跑 最大费用最大流或者 二分图带权匹配了

最后一点，这个题它卡常...

吸氧code:

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

const int N=204;

const int inf=0x3f3f3f3f;

const double finf=1e100;

int a[N][N],b[N][N],n,used[N],pre[N];

double l=0.0,r=0.0,dis[N];

struct node

{

    double c;

    int from,to,next,w;

}edge[N*N];

int head[N],cnt=-1;

void add(int u,int v,double c,int w)

{

    edge[++cnt].to=v;edge[cnt].from=u;edge[cnt].w=w;edge[cnt].c=c;edge[cnt].next=head[u];head[u]=cnt;

    edge[++cnt].to=u;edge[cnt].from=v;edge[cnt].w=0;edge[cnt].c=-c;edge[cnt].next=head[v];head[v]=cnt;

}

queue <int > q;

bool spfa()

{

    memset(used,0,sizeof(used));

    memset(pre,0,sizeof(pre));

    while(!q.empty()) q.pop();

    for(int i=1;i<=2*n+1;i++) dis[i]=-finf;

    dis[0]=0;

    pre[0]=-1;

    used[0]=1;

    q.push(0);

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        used[u]=0;

        for(int i=head[u];i!=-1;i=edge[i].next)

        {

            int v=edge[i].to,w=edge[i].w;double c=edge[i].c;

            if(w&&dis[u]+c>dis[v])

            {

                dis[v]=dis[u]+c;

                pre[v]=i;

                if(!used[v])

                {

                    used[v]=1;

                    q.push(v);

                }

            }

        }

    }

    return dis[2*n+1]!=-finf;

}

bool check(double L)

{

    memset(head,-1,sizeof(head));

    cnt=-1;

    for(int i=1;i<=n;i++)

    {

        add(0,i,0,1);

        add(i+n,2*n+1,0,1);

    }

    for(int i=1;i<=n;i++)

        for(int j=1;j<=n;j++)

            add(i,j+n,double(a[i][j])-double(b[i][j])*L,1);

    double sum=0.0;

    while(spfa())

    {

        int now=2*n+1;

        while(pre[now]!=-1)

        {

            edge[pre[now]].w-=1;

            edge[pre[now]^1].w+=1;

            sum+=edge[pre[now]].c;

            now=edge[pre[now]].from;

        }

    }

    return sum<0.0;

}

int main()

{

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

        for(int j=1;j<=n;j++)

        {

            scanf("%d",&a[i][j]);

            r+=a[i][j];

        }

    for(int i=1;i<=n;i++)

        for(int j=1;j<=n;j++)

            scanf("%d",&b[i][j]);

    while(l+1e-7<r)

    {

        double mid=(l+r)/2.0;

        if(check(mid))

            r=mid;

        else

            l=mid;

    }

    printf("%lf\n",l);

    return 0;

}

2018.6.4

相关文章