新生舞会
Time Limit: 10 Sec Memory Limit: 128 MB
[Submit][Status][Discuss]
Description
学校组织了一次新生舞会，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值最大。
Input
第一行一个整数n。
接下来n行，每行n个整数，第i行第j个数表示a[i][j]。
接下来n行，每行n个整数，第i行第j个数表示b[i][j]。
Output
一行一个数，表示C的最大值。四舍五入保留6位小数，选手输出的小数需要与标准输出相等
Sample Input
3
19 17 16
25 24 23
35 36 31
9 5 6
3 4 2
7 8 9
19 17 16
25 24 23
35 36 31
9 5 6
3 4 2
7 8 9
Sample Output
5.357143
HINT
1<=n<=100,1<=a[i][j],b[i][j]<=10^4
Main idea
选择两个人<i,j>会获得A[i][j]，以及B[i][j]，选择后不能再选，要求使得ΣA[i][j]/ΣB[i][j]最大。
Solution
最大费用最大流的话，可以把权值取相反数，然后跑最小费用最大流。
Code
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
typedef long long s64; const int ONE = ;
const int EDG = ;
const double eps = 1e-;
const int INF = ; int n,m;
int A[ONE][ONE],B[ONE][ONE];
int next[EDG],first[ONE],go[EDG],from[EDG],pas[EDG],tot;
int vis[ONE],q[],pre[ONE],tou,wei;
double w[EDG],dist[ONE];
int S,T;
double Ans; inline int get()
{
int res=,Q=; char c;
while( (c=getchar())< || c>)
if(c=='-')Q=-;
if(Q) res=c-;
while((c=getchar())>= && c<=)
res=res*+c-;
return res*Q;
} int Add(int u,int v,int flow,double z)
{
next[++tot]=first[u]; first[u]=tot; go[tot]=v; pas[tot]=flow; w[tot]=z; from[tot]=u;
next[++tot]=first[v]; first[v]=tot; go[tot]=u; pas[tot]=; w[tot]=-z; from[tot]=v;
} bool Bfs()
{
for(int i=S;i<=T;i++) dist[i]=INF;
tou = ; wei = ;
q[] = S; vis[S] = ; dist[S] = ;
while(tou < wei)
{
int u = q[++tou];
for(int e=first[u];e;e=next[e])
{
int v=go[e];
if(dist[v] > dist[u]+w[e] && pas[e])
{
dist[v] = dist[u]+w[e]; pre[v] = e;
if(!vis[v])
{
q[++wei] = v;
vis[v] = ;
}
}
}
vis[u] = ;
}
return dist[T] != INF;
} double Deal()
{
int x = INF;
for(int e=pre[T]; go[e]!=S; e=pre[from[e]]) x = min(x,pas[e]);
for(int e=pre[T]; go[e]!=S; e=pre[from[e]])
{
pas[e] -= x;
pas[((e-)^)+] += x;
Ans += w[e]*x;
}
} int Check(double ans)
{
memset(first,,sizeof(first)); tot=;
S=; T=*n+;
for(int i=;i<=n;i++)
{
Add(S,i,,);
for(int j=;j<=n;j++)
Add(i,j+n, ,-(A[i][j] - ans*B[i][j]));
Add(i+n,T,,);
} Ans = ;
while(Bfs()) Deal();
return -Ans >= eps;
} int main()
{
n=get();
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
A[i][j] = get();
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
B[i][j] = get(); double l = , r = 1e4;
while(l < r - 1e-)
{
double mid = (l+r)/2.0;
if(Check(mid)) l = mid;
else r = mid;
} if(Check(r)) printf("%.6lf", r);
else printf("%.6lf", l);
}