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
19 17 16
25 24 23
35 36 31
9 5 6
3 4 2
7 8 9
Sample Output
5.357143
pre.cjk { font-family: “Droid Sans Fallback”, monospace }
p { margin-bottom: 0.25cm; line-height: 120% }
a:link { }
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 }