BZOJ 4819 新生舞會，bzoj4819新生舞會

BZOJ 4819 新生舞會，bzoj4819新生舞會

第一句話:算出3.363636的孩子啊，你跑錯流種了。

貌似上一篇我講SDOI出原題？嘿還真是！

半個月前有一個叫WG的男人給我們搞過一場考試... ...

裡面有一道題叫做保密... ...SDOI2011... ...

對於每個點求ΣS/ΣT最值然後轉跑浮點數網絡流... ...

是不是感覺我在講這道題的正解... ...沒錯正解就是這樣... ...所以我說是原題吧。

跟 保密 是一樣的思路。求Σa/Σb的最值，可以用二分答案來做。

Σa/Σb的最大值怎麼求呢？設一個當前答案ans;

顯然如果有方案使Σa/Σb>ans則答案更優。

把式子化一下得：

Σa>Σb*ans;

即

Σa-Σb*ans>0;

即

Σ(a-b*ans)>0;

每次重新建圖或者帶著二分的mid跑最大費用最大流即可。

沒錯跑出3.363636是跑的最小費用最大流... ...別問我怎麼知道的。

用KM算法算最大權匹配跑的更快奈何我不會。好在它是一個左右相等的完全二分圖，用費用流做也是可以的。

出題人良心發現沒有卡費用流真是資磁。

還有就是浮點數二分答案跟整數不一樣，要用eps。

有哪位大佬能夠告訴我 為什麼我的費用流 跑的那麼慢嗎？

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <cstring>
#define LL long long
#define dob double
using namespace std;
 
const int N = 110;
const int M = 100010;
const dob eps = 1e-7;
const dob dobInf = 19260817.2333;
struct Node{int to,C;double val;int next;}E[M];
int head[M],tot,n,S,T,up[M],In[M];
dob a[N][N],b[N][N],far[M],Ans;
 
int gi()
{
    int x=0,res=1;char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')res=-res;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
    return x*res;
}
 
inline void link(int u,int v,int c,double val)
{
    E[++tot]=(Node){v,c,val,head[u]};
    head[u]=tot;
    E[++tot]=(Node){u,0,-val,head[v]};
    head[v]=tot;
}
 
inline void slink(double Eps)
{
    memset(head,0,sizeof(head));tot=1;
    for(int i=1;i<=n;++i)
        {
            link(S,i,1,0.0000000);
            link(i+n,T,1,0.0000000);
            for(int j=1;j<=n;++j)
                link(i,n+j,1,(a[i][j])-Eps*b[i][j]);
        }
}

inline bool spfa()
{
    for(int i=0;i<=T;++i)
        far[i]=-dobInf;
    memset(up,0,sizeof(up));
    queue<int>Q;Q.push(S);
    far[S]=0.000000;In[S]=1;
    while(!Q.empty())
        {
            int x=Q.front();Q.pop();
            for(int e=head[x];e;e=E[e].next)
                if(E[e].C && far[x]+E[e].val>far[E[e].to])
                    {
                        up[E[e].to]=e;
                        far[E[e].to]=far[x]+E[e].val;
                        if(!In[E[e].to])
                            Q.push(E[e].to),In[E[e].to]=1;
                    }
            In[x]=0;
        }
    if(!up[T])return false;
    for(int i=T;i^S;i=E[up[i]^1].to)
        E[up[i]].C--,E[up[i]^1].C++;
    Ans-=far[T];return true;
}
 
inline bool check()
{
    Ans=0.00;
    while(spfa())
        if(Ans>=0.00)return true;
    return Ans>=0.00;
}
 
int main()
{
    n=gi();S=2*n+1,T=2*n+2;
    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]);
    dob l=0.0,r=10000,ans=r;
    while(r-l>eps)
        {
            double mid=(l+r)/2.0;
            slink(mid);
            if(check())r=mid,ans=mid;
            else l=mid;
        }
    printf("%.6lf\n",ans);
    return 0;
}