洛谷 P3705 [SDOI2017]新生舞会 题解【网络流】【分数规划】
点击量：280
这个题是主要是考01分数规划和网络流建模。
题目描述
学校组织了一次新生舞会，Cathy作为经验丰富的老学姐，负责为同学们安排舞伴。
有n个男生和n个女生参加舞会,每一个男生和一个女生一起跳舞，互为舞伴。
Cathy收集了这些同学之间的关系，比如两个人之前认识没计算得出$ a_{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=\frac{a’_1+a’_2+…+a’_n}{b’_1+b’_2+…+b’_n}$
Cathy希望C值最大。
输入输出格式
输入格式：
第一行一个整数n。
接下来n行，每行n个整数，第i行第j个数表示$ a_{i,j}$。
接下来n行，每行n个整数，第i行第j个数表示$ b_{i,j}$。
输出格式：
一行一个数，表示C的最大值。四舍五入保留6位小数，选手输出的小数需要与标准输出相等。
输入输出样例
输入样例#1：319 17 1625 24 2335 36 319 5 63 4 27 8 9输出样例#1：5.357143说明
对于10%的数据， $ 1\le n\le 5$
对于40%的数据， $ 1\le n\le 18$
另有20%的数据， $ b_{i,j}\le 1$
对于100%的数据， $ 1\le n\le 100,1\le a_{i,j},b_{i,j}\le 10^4$
首先这个题需要匹配，而所有的男生和女生间都可以互相匹配，而每个男生只找一个女生，这就是二分图匹配，并且有$ n$对和$ n^2$条边。而要跑的是最佳匹配，就需要题目中所说的“C值最大”。
C是由$ a_{i,j}$和$ b_{i,j}$确定的，因此我们要选择使C最大的n条边，这就是分数规划问题。
分数规划问题是这样的，设一共有n个元素，每个元素可以选或不选，选择第i个元素会对分子加上$ a_i$，对分母加上$ b_i$。这样就可以将这种状况抽象成一个模型：共取k个数，令$ L=\frac{\sum^{k}_{i=1}a_i}{\sum^{k}_{i=1}b_i}$，在不能确定k的情况下，这是不好预估的，那么我们将要选的元素，附加一个权值$ x_i$，如果选择这个元素，将$ x_i$置1，不选置0。我们的L就会变成$ L=\frac{\sum^{n}_{i=1}a_i\times x_i}{\sum^{n}_{i=1}b_i\times x_i}$。
将上述式子变形，得到$ \sum^{n}_{i=1}a_i\times x_i =L\times \sum^{n}_{i=1}b_i\times x_i$，将L乘进去，得到$ \sum^{n}_{i=1}a_i\times x_i =\sum^{n}_{i=1}L\times b_i\times x_i$。因此，如果$ f=\sum^{n}_{i=1}a_i\times x_i -\sum^{n}_{i=1}L\times b_i\times x_i>0$那么L还有增加的余地，如果小于0，说明L不能满足这一条件，取不到而越界，L必须要减小。
上述情况，我们可以用二分答案来缩小L的区间，上界是预估的极端情况。
而一般最后的答案都是保留t位小数，我们只需要设置eps=1e-(t+1)即可。
那么选一对男女生$ (i,j)$，给$ f$增加了$ a_{i,j}-L\times b{i,j}$的代价，而我们在上面提到这里要找二分图完备最大权值匹配，这个模型就可以建出来了。
和二分图匹配跑最大流一样，建出一个源点为0，汇点为$ t\notin[0,2n]$的网络流，0和t连边的花费为0，其他花费为$ a_{i,j}-L\times b{i,j}$，每个男生和女生连接花费为$ a_{i,j}-L\times b{i,j}$的边，所有边权值为1。因为是完备匹配，所以最大流一定是n。随着L的改变，图的权值也会改变，所以每次检验L时都要重新构图。
如果最终$ f=\sum^{n}_{i=1}a_i\times x_i -\sum^{n}_{i=1}L\times b_i\times x_i$的结果大于0，说明L还有增大的余地，将l置为mid，如果小于0，则不成立。
值得注意的是，跑费用流的时候，一定要把所有spfa跑完，并且需要把dis的初始值设为$ -\infty $不然是错的。。。
还有，这个题是稠密图，因此邻接矩阵会比邻接表快。。。邻接表卡常很严重。。
Code:
#include<cstdio>
#include<cstring>
#include<deque>
using std::deque;
int v[205][205];
double w[205][205];
int t=201,n;//统一以t为汇点
int a[201][201],b[201][201];
int pre[220];
bool used[220];
double ans=0.0;
double dis[220];
bool spfa()
{
dis[0]=0.0;
for(int i=1;i<=201;i++)//需要赋值负无穷，不然不能更新。
dis[i]=-1000000;
pre[0]=0;
memset(used,0,sizeof(used));
deque<int> q;
q.push_back(0);
while(!q.empty())
{
int k=q.front();
q.pop_front();
used[k]=false;
for(int i=1;i<=201;(i==2*n)?i=201:i++)
{
if(v[k][i]>0&&dis[i]<dis[k]+w[k][i])
{
dis[i]=dis[k]+w[k][i];
pre[i]=k;
if(!used[i])
{
if(q.empty()||dis[i]<dis[k])//spfa玄学优化
q.push_front(i);
else
q.push_back(i);
used[i]=true;
}
}
}
}
if(dis[201]==-1000000)//说明此次spfa找不到到t的最短路
return false;
return true;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=n+1;j<=2*n;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
for(int j=n+1;j<=2*n;j++)
scanf("%d",&b[i][j]);
double l=0.0,r=20000.0,mid;
double eps=1e-7;//设置精度
while(r-l>eps)//分数规划的二分
{
mid=(l+r)/2.0;
for(int i=1;i<=n;i++)//初始化源点流出边
{
v[0][i]=1;
w[0][i]=0.0;
v[i][0]=0;
w[i][0]=0.0;
}
for(int i=n+1;i<=2*n;i++)//初始化汇点流入边
{
v[i][201]=1;
w[i][201]=0.0;
v[201][i]=0;
w[201][i]=0.0;
}
for(int i=1;i<=n;i++)
for(int j=n+1;j<=2*n;j++)//建网络流
{
v[i][j]=1;
w[i][j]=a[i][j]-mid*b[i][j];
v[j][i]=0;
w[j][i]=-(a[i][j]-mid*b[i][j]);//反边的费用也是反的
}
ans=0.0;
while(spfa())//最大费用流
{
int p=201;
while(p!=NULL)
{
v[pre[p]][p]--;
v[p][pre[p]]++;
p=pre[p];
}
ans+=dis[201];
}
if(ans>0)
l=mid;
else
r=mid;
}
printf("%.6lf\n",l);
return 0;
}
说点什么