题解 P3705 【[SDOI2017]新生舞会】
nianheng
2018-05-06 17:33:28
### 分数规划，最大费用最大流#
题意可以简化为给出一个矩阵，要求每行和每列必须且只能取一个格子，要求$sigma\ a_{i,j}/sigma\ b_{i,j}$ 最大
考虑分数规划，可以将式子转化：
$sigma\ a_{i,j}/sigma\ b_{i,j}=C$
$sigma\ a_{i,j}=sigma\ b_{i,j}*C$
$sigma\ a_{i,j}-sigma\ b_{i,j}*C=0$
$sigma(\ a_{i,j}-b_{i,j}*C)=0$
C就是我们要求的最大值，我们可以$mid$实数二分它，对于每一个$mid$，求出这种情况下$sigma(\ a_{i,j}-b_{i,j}*mid)=0$的最大值，如果最大值小于0，就说明$mid>C$，反之亦然。
至于怎么求最大值，可以将横坐标建一个点集，纵坐标建一个点集，对于每个矩阵上的点$a_{i,j}$建一条从i到j的弧，流量为1，费用为$a_{i,j}-sigma\ b_{i,j}*mid$，然后跑最大费用最大流就行了
代码：
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#define inf 0x7fffffff
using namespace std;
inline int read()
{
int ans=0,fh=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
fh=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();
return ans*fh;
}
const int maxn=300;
const int maxm=10010;
const double eps=0.00000001;
int s,t,v[maxm*2],u[maxm*2],w[maxm*2],qq[maxn],ll[maxn],nex[maxm*2],head[maxn],num=1,n,a[110][110],b[110][110];
double f[maxm*2],bj[maxn],l,r,mid;
bool cz[maxn];
queue<int>q;
void add(int x,int y,double fee)
{
u[++num]=x;
v[num]=y;
w[num]=1;
f[num]=fee;
nex[num]=head[x];
head[x]=num;
u[++num]=y;
v[num]=x;
w[num]=0;
f[num]=-fee;
nex[num]=head[y];
head[y]=num;
}
bool spfa()
{
memset(qq,0,sizeof(qq));
for(int i=1;i<=n*2+2;i++)
bj[i]=2100000000;
memset(ll,0,sizeof(ll));
q.push(s);
bj[s]=0;
ll[s]=inf;
while(!q.empty())
{
int now=q.front();
q.pop();
cz[now]=0;
for(int i=head[now];i;i=nex[i])
if(w[i]&&bj[v[i]]>bj[now]+f[i])
{
bj[v[i]]=bj[now]+f[i];
ll[v[i]]=min(w[i],ll[now]);
qq[v[i]]=i;
if(!cz[v[i]])
q.push(v[i]),cz[v[i]]=1;
}
}
return qq[t]>0;
}
double EK()
{
double fee=0;
while(spfa())
{
int liu=ll[t];
for(int i=qq[t];i;i=qq[u[i]])
w[i]-=liu,w[i^1]+=liu;
fee+=liu*bj[t];
}
return fee*-1;
}//最大费用最大流
double work(double x)
{
memset(head,0,sizeof(head));
num=1;
for(int i=1;i<=n;i++)
add(s,i,0),add(i+n,t,0);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
add(i,j+n,(double)x*b[i][j]-a[i][j]);//建图
return EK();
}
int main()
{
n=read();
s=n*2+1;t=s+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
b[i][j]=read();
r=1000000;
while(r-l>eps)
{
mid=(l+r)*0.5;
double dd=work(mid);
if(dd>=0)
l=mid;
else
r=mid;
}//实数二分
printf("%.6lf",l);
fclose(stdin);
return 0;
}
```