题解 P3705 【[SDOI2017]新生舞会】

· · 题解

不知道为什么我一吸氧就开始疯狂炸……

(总之是在没有O_{2}的情况下疯狂卡常过了这道题)

01分数规划

看起来这道题似乎非常的不可做

但是熟练的OIER应该一眼就可以推出做法吧

首先我们发现题目中给出的式子是这样的

最大化

Mid=\frac{\sum a_{i,j}}{\sum b_{i,j}}

那么我们可以认为这是一个网格图，每个格子上有一个物品，价值为a_{i,j},代价为b_{i,j}现在要求你每一行每一列取且仅能取一个，求Mid最大值

如果你学习过一种叫01分数规划的东西的话，你会意识到，处理这类问题第一反应是二分答案，更准确的来讲，我们判断我们二分的答案mid是否比真实答案大，这样就可以求出这个函数的值了

让我们来试着变换下刚才的式子

\sum a_{i,j}-\sum Midb_{i,j}=0

也就是说如果mid=c，那么这个式子最大值会等于0

如果mid>c这个式子最大值会小于0

如果mid<c这个式子最大值会大于0

然后我们就可以就此二分答案了

唯一要解决的问题是，在给定mid的前提下如何求出刚才那个式子的最大值

显然我们可以把一个格子的权值变成a_{i,j}-Midb_{i,j}现在唯一要考虑的问题就是如何满足每一行每一列取且仅能取一个的前提下做到最优

这里我们需要使用网络流描述一个互斥的关系，如果你足够熟练的话应该可以很快反应过来这是行列拆点

具体来讲我们把每一行和每一列看作点，每一个点看作行列间的一条边，那么我们如果从源点向所有行点连一条容量为1的边，所有列点向汇点连一条容量为1的边，那么我们会发现这样可以满足每个行列都只选一次的限制条件

剩下的事情就是把每个点作为一个容量为1的点连入，然后点权作为边权跑费用流就好了

(不就是二分图最大带权匹配吗……会的话不需要我多说吧)

卡常数

本题唯一的难点在于丧心病狂的10^{-6}精度要求，因此我们的二分次数将不可避免的多

具体来讲卡常数的办法就是去掉你程序里的全部结构题再手写一个队列，依靠信仰可以通过卡常来通过本题

上代码~

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;const int N=110;typedef double db;db eps=1e-8;int n;
int v[4*N*N];int x[4*N*N];int c[4*N*N];db val[4*N*N];
int al[2*N];int ct=1;int rst[4*N*N];//去掉了所有的结构体，大家凑合着看吧 
inline void add(int p,int y)
{
    v[++ct]=y;x[ct]=al[p],c[ct]=1;al[p]=ct;rst[ct]=1;
    v[++ct]=p;x[ct]=al[y];c[ct]=0;al[y]=ct;rst[ct]=0;
}db cost;db d[2*N];int s;int t;int ctt;int q[4000010];int hd=1;int til;
int fr[2*N];int nu[2*N];bool book[2*N];
inline bool spfa()
{
    for(int i=1;i<=ctt;i++){d[i]=-0x3f3f3f3f;}d[s]=0;
    for(q[++til]=s;hd<=til;++hd)//这里手写了队列…… 
    {
        for(int w=q[hd],i=al[w];i;i=x[i])//spfa不说了 
        {
            if(d[v[i]]<d[w]+val[i]&&c[i]!=0)
            {
                fr[v[i]]=w;nu[v[i]]=i;d[v[i]]=d[w]+val[i];
                if(!book[v[i]]){q[++til]=v[i];book[v[i]]=true;}
            }
        }book[q[hd]]=false;
    }hd=1;til=0;//记得手动清空 
    if(d[t]==-0x3f3f3f3f){return false;}//这里为了省常数直接+1-1因为边权只有1和0 
    for(int p=t;p!=s;p=fr[p]){c[nu[p]]-=1;c[nu[p]^1]+=1;}
    cost+=d[t];return true;
}db a[N][N];db b[N][N];int tr[N][N];
inline void rebuild(db mid)//这里维护了一个点到边的映射 
{
    for(int i=1;i<=ct;i++){c[i]=rst[i];}
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)//重新设置下边权 
        {
            val[tr[i][j]]=a[i][j]-b[i][j]*mid;
            val[tr[i][j]^1]=-val[tr[i][j]];
        }
    }cost=0;
}
int main()
{
    scanf("%d",&n);ctt=2*n;s=++ctt;t=++ctt;
    for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf("%lf",&a[i][j]);}}
    for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf("%lf",&b[i][j]);}}
    for(int i=1;i<=n;i++){add(s,i);add(n+i,t);}//加边 
    for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){add(i,n+j);tr[i][j]=ct-1;}}
    db l=0;db r=1e4;
    while(r-l>eps)//二分答案 
    {
        db mid=(l+r)/2;rebuild(mid);
        while(spfa());if(cost<0){r=mid;}else {l=mid;}
    }printf("%.6lf",l);return 0;//拜拜程序~ 
}