题目描述

学校组织了一次新生舞会，Cathy作为经验丰富的老学姐，负责为同学们安排舞伴。

有个男生和个女生参加舞会买一个男生和一个女生一起跳舞，互为舞伴。

Cathy收集了这些同学之间的关系，比如两个人之前认识没计算得出 

Cathy还需要考虑两个人一起跳舞是否方便，比如身高体重差别会不会太大，计算得出 ，表示第i个男生和第j个女生一起跳舞时的不协调程度。

当然，还需要考虑很多其他问题。

Cathy想先用一个程序通过和求出一种方案，再手动对方案进行微调。

Cathy找到你，希望你帮她写那个程序。

一个方案中有n对舞伴，假设没对舞伴的喜悦程度分别是，假设每对舞伴的不协调程度分别是。令

Cathy希望C值最大。

输入输出格式

输入格式：

第一行一个整数n。

接下来n行，每行n个整数，第i行第j个数表示。

接下来n行，每行n个整数，第i行第j个数表示。

 

输出格式：

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

 

输入输出样例

输入样例#1：

319 17 1625 24 2335 36 319 5 63 4 27 8 9

输出样例#1：

5.357143

说明

对于10%的数据，

对于40%的数据，

另有20%的数据，

对于100%的数据，

思路：二分答案+费用流

一开始，边的费用没有想到，其实移一下项就好了。

然后，就见识到了什么叫卡常数，蒟蒻常数巨大。。。

于是就开始借鉴大佬的优化，发现大佬写的是紫书上的板子，果然，手模代码不靠谱吗？

丧失OI路的信心。

事实证明：结构体是极慢的。

 7.3s->4.1s

代码实现：

1 #include
     
       2 #include
      
        3 #include
       
         4 #define inf -1e9 5 using namespace std; 6 const int maxn=110; 7 const int maxm=maxn*maxn<<2; 8 queue
        
         q; 9 int n,s,t,a,b;10 double l,r,mid,ans,error=1e-7;11 int map[maxn][maxn][2],h[maxn*maxn<<1],hs=1;12 int e_q[maxm],e_z[maxm],e_n[maxm],p[maxn<<1];13 bool e_w[maxm],v[maxn<<1];14 double e_f[maxm],w[maxn<<1];15 char r_w[30],r_l;16 int read(int &x){17     while(r_w[0]=getchar(),r_w[0]<'0'||r_w[0]>'9');r_l=1;18     while(r_w[r_l]=getchar(),r_w[r_l]>='0'&&r_w[r_l]<='9') r_l++;19     for(int i=0;i
         
          error){56         mid=(l+r)/2,ans=0;57         memset(h,0,sizeof(h)),hs=1;58         for(int i=1;i<=n;i++) add(s,i,0),add(i+n,t,0);59         for(int i=1;i<=n;i++)60         for(int j=1;j<=n;j++)61         add(i,j+n,map[i][j][0]-mid*map[i][j][1]);62         MCMF();63         if(ans>0) l=mid;64         else r=mid;65     }66     printf("%.6lf",r);67     return 0;68 }
         
        
       
      
     

傻逼题我都改了这么久，药丸药丸。