题目描述
学校组织了一次新生舞会，Cathy作为经验丰富的老学姐，负责为同学们安排舞伴。有n个男生和n个女生参加舞会买一个男生和一个女生一起跳舞，互为舞伴。Cathy收集了这些同学之间的关系，比如两个人之前认识没计算得出 a[i][j] ，表示第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=(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]。
1<=n<=100,1<=a[i][j],b[i][j]<=10^4
输出
一行一个数，表示C的最大值。四舍五入保留6位小数，选手输出的小数需要与标准输出相等
样例输入
3
19 17 16
25 24 23
35 36 31
9 5 6
3 4 2
7 8 9
样例输出
5.357143
题解
分数规划+费用流
二分答案mid，将每个点的值看作a-b*mid。
由于每个男生只能搭配一名不同的女生，所以问题可以转化为：1个n*n的矩阵中每个位置都有1个数，求选出n个彼此不在同一行或同一列的数的和的最大值是多少。
加边s->i(1,0),i+n->t(1,0)，i->j+n(1，v[i][j])，跑最大费用最大流，若大于0则调整下界，否则调整上界，直至上下界基本重合。
证明：如果最大费用大于0，则∑(v[ik][jk])>0，即∑(a[ik][jk]-b[ik][jk]*mid)>0，即∑a[ik][jk]>∑b[ik][jk]*mid，即∑a[ik][jk]/∑b[ik][jk]＞mid，故需要调整下界来进一步更新答案，否则调整上界来调整答案。
#include <cstdio>
#include <cstring>
#include <queue>
#define eps 1e-7
using namespace std;
queue<int> q;
int n , head[210] , to[30000] , val[30000] , next[30000] , cnt , s , t , from[210] , pre[210];
double a[110][110] , b[110][110] , cost[30000] , dis[210];
void add(int x , int y , int v , double c)
{
to[++cnt] = y , val[cnt] = v , cost[cnt] = c , next[cnt] = head[x] , head[x] = cnt;
to[++cnt] = x , val[cnt] = 0 , cost[cnt] = -c , next[cnt] = head[y] , head[y] = cnt;
}
bool spfa()
{
int x , i;
for(i = s ; i <= t ; i ++ ) from[i] = -1 , dis[i] = 10000000.0;
dis[s] = 0 , q.push(s);
while(!q.empty())
{
x = q.front() , q.pop();
for(i = head[x] ; i ; i = next[i])
if(val[i] && dis[to[i]] > dis[x] + cost[i])
dis[to[i]] = dis[x] + cost[i] , from[to[i]] = x , pre[to[i]] = i , q.push(to[i]);
}
return ~from[t];
}
double mincost()
{
int k , i;
double ans = 0;
while(spfa())
{
k = 0x3f3f3f3f;
for(i = t ; i != s ; i = from[i]) k = min(k , val[pre[i]]);
ans += k * dis[t];
for(i = t ; i != s ; i = from[i]) val[pre[i]] -= k , val[pre[i] ^ 1] += k;
}
return ans;
}
bool judge(double mid)
{
int i , j;
memset(head , 0 , sizeof(head));
cnt = 1;
for(i = 1 ; i <= n ; i ++ ) add(s , i , 1 , 0);
for(i = 1 ; i <= n ; i ++ ) add(i + n , t , 1 , 0);
for(i = 1 ; i <= n ; i ++ )
for(j = 1 ; j <= n ; j ++ )
add(i , j + n , 1 , mid * b[i][j] - a[i][j]);
return mincost() < 0;
}
int main()
{
int i , j;
double l = 0.0 , r = 10000000.0 , mid;
scanf("%d" , &n);
s = 0 , t = 2 * n + 1;
for(i = 1 ; i <= n ; i ++ ) for(j = 1 ; j <= n ; j ++ ) scanf("%lf" , &a[i][j]);
for(i = 1 ; i <= n ; i ++ ) for(j = 1 ; j <= n ; j ++ ) scanf("%lf" , &b[i][j]);
while(l <= r)
{
mid = (l + r) / 2;
if(judge(mid)) l = mid + eps;
else r = mid - eps;
}
printf("%.6lf\n" , (l + r) / 2);
return 0;
}