首页 > 代码库 > [BZOJ]4819: [Sdoi2017]新生舞会

[BZOJ]4819: [Sdoi2017]新生舞会

Time Limit: 10 Sec  Memory Limit: 128 MB

Description

  学校组织了一次新生舞会,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值最大。

Input

  第一行一个整数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

Output

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

Sample Input

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

Sample Output

  5.357143

Solution

  知道分数规划后这题应该是纯送的吧。但很悲催的是我看这题的时候并不知道。最难受的是我在APIO2017考前试机的时候因为网络故障登不上练习赛网站,于是打开BZOJ看到了这题,看了看不会做,打算之后慢慢想,结果第二天就考到了一道分数规划,大家都说是SB题,100多人A了,我爆0。要是A了这题我貌似就金了233(可惜实际上是铜牌垫底)。一个是自己姿势水平太低,一个是自己懒,没有当天就把这题做掉吧。真是个悲伤的故事。
  然后说这题,我们二分一个答案,连边a[i][j]-b[i][j]*ans用费用流跑二分图带权匹配,算出来最大费用小于0说明答案偏大,否则答案偏小。为什么这么做呢?百度分数规划,个人感觉还是很好理解的……(以我这弱菜水平大概也只花了5分钟看分数规划+5秒钟想这题吧)

Code

#include<cstdio>
#include<cstring>
#include<cmath>
inline int read()
{
    int x;char c;
    while((c=getchar())<0||c>9);
    for(x=c-0;(c=getchar())>=0&&c<=9;)x=x*10+c-0;
    return x;
}
#define MN 100
#define MV 200
#define ME 10200
#define S MV+1
#define T MV+2
struct edge{int nx,t,w;double c;}e[ME*2+5];
int a[MN+5][MN+5],b[MN+5][MN+5],h[MV+5],en,q[MV+5],qn,inq[MV+5],rw[MV+5];
double d[MV+5];
inline void ins(int x,int y,int w,double c)
{
    e[++en]=(edge){h[x],y,w,c};h[x]=en;
    e[++en]=(edge){h[y],x,0,-c};h[y]=en;
}
inline int next(int x){return x==MV+4?0:x+1;}
inline int prev(int x){return x?x-1:MV+4;}
bool spfa()
{
    int i,j,x;
    for(i=1;i<=T;++i)d[i]=1e18;
    for(d[q[qn=1,i=0]=S]=0;i!=qn;inq[x]=0,i=next(i))
        for(j=h[x=q[i]];j;j=e[j].nx)if(e[j].w&&d[x]+e[j].c<d[e[j].t])
        {
            d[e[j].t]=d[x]+e[j].c;rw[e[j].t]=j;
            if(!inq[e[j].t])if(d[e[j].t]<=d[q[i]])inq[q[i]=e[j].t]=1,i=prev(i);
            else inq[q[qn]=e[j].t]=1,qn=next(qn);
        }
    return d[T]<1e18;
}
int main()
{
    int n=read(),i,j;double l,r,mid,ans;
    for(i=1;i<=n;++i)for(j=1;j<=n;++j)a[i][j]=read();
    for(i=1;i<=n;++i)for(j=1;j<=n;++j)b[i][j]=read();
    for(l=0,r=1e6;r-l>1e-7;)
    {
        mid=(l+r)/2;
        memset(h,0,sizeof(h));en=1;
        for(i=1;i<=n;++i)ins(S,i,1,0),ins(i+n,T,1,0);
        for(i=1;i<=n;++i)for(j=1;j<=n;++j)ins(i,j+n,1,b[i][j]*mid-a[i][j]);
        for(ans=0;spfa();)for(ans+=d[T],i=T;i!=S;i=e[rw[i]^1].t)--e[rw[i]].w,++e[rw[i]^1].w;
        (ans<0?l:r)=mid;
    }
    printf("%.6lf",l);
}

 

[BZOJ]4819: [Sdoi2017]新生舞会