[Sdoi2017]新生舞会

4819: [Sdoi2017]新生舞会

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 259 Solved: 132
[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]求出一种方案，再手动对方案进行微调。C

athy找到你，希望你帮她写那个程序。一个方案中有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]。

1<=n<=100,1<=a[i][j],b[i][j]<=10^4

Output

一行一个数，表示C的最大值。四舍五入保留6位小数，选手输出的小数需要与标准输出相等

Sample Input

3
19 17 16
25 24 23
35 36 31
9 5 6
3 4 2
7 8 9

Sample Output

5.357143

a1+a2+...+an>ans*(b1+b2+b3+...+bn)时，可以更新ans。

然后就可以二分了，每次二分一个答案跑费用流。

显然这是一个二分图，A部和B部的每个点之间连边，容量为1，费用为0，S与A部，B部与T连边，容量为1，费用为a-ans*b。

常数大的飞起的代码。

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <cstdlib>
  4 #include <cstring>
  5 #include <cstdio>
  6 #include <cmath>
  7 #include <queue>
  8 #define maxn 210
  9 #define inf 1999999999.0
 10 #define RG register
 11 using namespace std;
 12 struct data{
 13   int nex,to,w;
 14   double a,b;
 15 }g[maxn*maxn*2],e[maxn*maxn*2];
 16 double a[maxn][maxn],b[maxn][maxn],dis[maxn];
 17 int head[maxn],edge=-1,vis[maxn],pre[maxn];
 18 int q[maxn*maxn];
 19 inline int Read() {
 20   int w;bool q=1;char c;
 21   while (((c=getchar())<'0'||'9'<c)&&c!='-');
 22   if (c=='-') q=0,c=getchar();
 23   w=c-'0';
 24   while ('0'<=(c=getchar())&&c<='9') w=w*10+c-'0';
 25   return q?w:-w;
 26 }
 27 inline void add(int from,int to,int w,int a,int b){
 28   g[++edge].nex=head[from];
 29   g[edge].to=to;
 30   g[edge].w=w;
 31   g[edge].a=a;
 32   g[edge].b=b;
 33   head[from]=edge;
 34 }
 35 inline bool SPFA(int s,int t,double kp){
 36   for(int i=0;i<=t;i++)
 37     dis[i]=-inf;
 38   double zd=dis[0];
 39   dis[s]=0,vis[s]=1;
 40   int h=0,tt=1;
 41   q[tt]=s;
 42   while(h<tt){
 43     int u=q[++h];
 44     vis[u]=0;
 45     for(RG int i=head[u];i!=-1;i=e[i].nex)
 46       if(e[i].w>0 && dis[e[i].to]<dis[u]+(e[i].a-kp*e[i].b)){
 47     dis[e[i].to]=dis[u]+(e[i].a-kp*e[i].b);
 48     pre[e[i].to]=i;
 49     if(!vis[e[i].to]){
 50       vis[e[i].to]=1;
 51       q[++tt]=e[i].to;
 52     }
 53       }
 54   }
 55   if(dis[t]==zd) return 0;
 56   else return 1;
 57 }
 58 inline double end(int s,int t,double kp){
 59   int p,sum=inf;
 60   double ans=0.0;
 61   for(RG int u=t;u!=s;u=e[p^1].to)
 62     p=pre[u],sum=min(sum,e[p].w);
 63   for(RG int u=t;u!=s;u=e[p^1].to){
 64     p=pre[u];
 65     e[p].w-=sum;
 66     e[p^1].w+=sum;
 67     ans+=sum*(e[p].a-kp*e[p].b);
 68   }
 69   return ans;
 70 }
 71 inline double solve(int s,int t,double kp){
 72   double ans=0.0;
 73   while(SPFA(s,t,kp))
 74     ans+=end(s,t,kp);
 75   return ans;
 76 }
 77 int main()
 78 {
 79   freopen("ball.in","r",stdin);
 80   freopen("ball.out","w",stdout);
 81   int n;
 82   scanf("%d",&n);
 83   memset(head,-1,sizeof(head));
 84   int s=0,t=2*n+1;
 85   for(RG int i=1;i<=n;i++)
 86     for(RG int j=1;j<=n;j++) a[i][j]=Read();
 87   for(RG int i=1;i<=n;i++)
 88     for(RG int j=1;j<=n;j++) b[i][j]=Read();
 89   for(RG int i=1;i<=n;i++)
 90     for(RG int j=n+1;j<=2*n;j++)
 91       add(i,j,1,a[i][j-n],b[i][j-n]),add(j,i,0,-a[i][j-n],-b[i][j-n]);
 92   for(RG int i=1;i<=n;i++) add(s,i,1,0,0),add(i,s,0,0,0),add(i+n,t,1,0,0),add(t,i+n,0,0,0);
 93   RG double r=10000.0,l=0.0;
 94   int T=36;
 95   while(T){
 96     memcpy(e,g,sizeof(g));
 97     T--;
 98     double mid=(l+r)/2;
 99     if(solve(s,t,mid)>=0) l=mid;
100     else r=mid;
101   }
102   printf("%.6lf",r);
103   return 0;
104 }