题解 P3705 【[SDOI2017]新生舞会】
VenusM1nT
2019-01-25 13:31:04
二分图最佳匹配 + 分数规划。读题，发现要求最优配对，很显然，这个图是一张二分图，那么最佳匹配我们可以用 $\text{KM}$ 或者 费用流 来求出，这里不赘述如何求出最佳匹配。我们来考虑怎么计算这个 $C=\frac{\sum_{i=1}^{k}a'[i]}{\sum_{i=1}^{k}b'[i]}$。显然，这里的 $\sum_{i=1}^{k}b'[i]$ 是非常不好处理的，所以我们要引入**分数规划**的思想，将这个式子转化成 $\sum_{}^{}a'-C\sum_{}^{}b'=0$，然后二分答案 $C$，每次 $\text{Check}$ 都跑一遍最佳匹配，边权就设成 $a[i][j]-mid\times b[i][j]$，然后跑最大权最佳匹配（也就是最大费用最大流），判断最后得到的权和是否为 $0$ 即可。
同步发表于笔者的博客：[题解 P3705 [SDOI2017]新生舞会](https://venusnero.github.io/2019/01/25/solution_p3705/)
代码选用 $\text{zkw}$ 费用流。
```cpp
#include<bits/stdc++.h>
#define MAXN 1005
#define inf 1010580540
#define eps 1e-8
using namespace std;
deque <int> q;
int cnt,fst[MAXN],nxt[MAXN<<5],to[MAXN<<5],w[MAXN<<5],cur[MAXN];
int n,m,S,T,maxflow;
double dis[MAXN],a[MAXN][MAXN],b[MAXN][MAXN],cot[MAXN<<5],mincost;
bool inq[MAXN],vis[MAXN];
void AddEdge(int u,int v,int c,double fl)
{
to[++cnt]=v;
nxt[cnt]=fst[u];
fst[u]=cnt;
w[cnt]=c;
cot[cnt]=fl;
}
bool Spfa()
{
for(int i=S;i<=T;i++) dis[i]=inf;
memset(inq,0,sizeof(inq));
q.push_front(T);
dis[T]=0;
inq[T]=1;
while(!q.empty())
{
int u=q.front();
q.pop_front();
inq[u]=0;
for(int i=fst[u];i;i=nxt[i])
{
int v=to[i];
if(dis[v]>dis[u]-cot[i] && w[i^1])
{
dis[v]=dis[u]-cot[i];
if(!inq[v])
{
if(!q.empty() && dis[v]<dis[q.front()]) q.push_front(v);
else q.push_back(v);
inq[v]=1;
}
}
}
}
return dis[S]!=inf;
}
int Dfs(int u,int flow)
{
vis[u]=1;
if(u==T || !flow) return flow;
int used=0;
for(int &i=cur[u];i;i=nxt[i])
{
int v=to[i];
if(dis[v]==dis[u]-cot[i] && w[i] && !vis[v])
{
int fl=Dfs(v,min(flow,w[i]));
if(fl)
{
used+=fl;
flow-=fl;
w[i]-=fl;
w[i^1]+=fl;
if(!flow) break;
}
}
}
return used;
}
void zkwMCMF()
{
while(Spfa())
{
vis[T]=1;
while(vis[T])
{
memset(vis,0,sizeof(vis));
memcpy(cur,fst,sizeof(fst));
int fl=Dfs(S,inf);
maxflow+=fl;
mincost+=dis[S]*fl;
}
}
mincost=-mincost;
}
bool Check(double mid)
{
maxflow=mincost=0;
cnt=1;
memset(fst,0,sizeof(fst));
for(int i=1;i<=n;i++)
{
AddEdge(S,i,1,0);
AddEdge(i,S,0,0);
}
for(int i=n+1;i<=n*2;i++)
{
AddEdge(i,T,1,0);
AddEdge(T,i,0,0);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
AddEdge(i,j+n,1,-a[i][j]+b[i][j]*mid);
AddEdge(j+n,i,0,a[i][j]-b[i][j]*mid);
}
}
zkwMCMF();
return fabs(mincost)<=eps || mincost>eps;
}
int main()
{
scanf("%d",&n);
S=0;
T=n*2+1;
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]);
}
double l=0,r=1e4;
while(r-l>eps)
{
double mid=(l+r)/2.0;
if(Check(mid)) l=mid;
else r=mid;
}
printf("%.6lf\n",r);
return 0;
}
```