首页 > 代码库 > [Sdoi2017]新生舞会
[Sdoi2017]新生舞会
[Sdoi2017]新生舞会
http://www.lydsy.com/JudgeOnline/problem.php?id=4819
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]求出一种方案，再手动对方案进行微调。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
01分数规划+费用流
ans=Σ a/ Σ b
Σ a=Σ（b*ans）
a1-b1*ans+a2-b2*ans+a3-b3*ans……=0
二分ans
以ai-bi*ans 为费用跑最大费用流
若费用>=0，则调整下界
否则，调整上界
#include<cstdio>#include<cstring>#include<queue>#include<algorithm>#include<iostream>#include<cmath>#include<cstdlib>#define eps 1e-8#define N 111#define M 11111using namespace std;int n,src,decc;double ans;int a[N][N],b[N][N];int front[N*2],next[M*4],to[M*4],tot,flow[M*4],pre[N*2],from[M*4];double cost[M*4],dis[N*2];int g[N*2];queue<int>q;bool v[N*2];void add(int u,int v,int w,double val){ to[++tot]=v; next[tot]=front[u]; front[u]=tot; flow[tot]=w; cost[tot]=val; from[tot]=u; to[++tot]=u; next[tot]=front[v]; front[v]=tot; flow[tot]=0; cost[tot]=-val; from[tot]=v;}bool spfa(){ for(int i=0;i<=2*n+1;i++) dis[i]=-1e9; memset(v,false,sizeof(v)); memset(g,0,sizeof(g)); q.push(src); v[src]=true; dis[src]=0; int now,t; while(!q.empty()) { now=q.front(); q.pop(); v[now]=false; for(int i=front[now];i;i=next[i]) { t=to[i]; if(dis[t]<dis[now]+cost[i]&&flow[i]>0) { dis[t]=dis[now]+cost[i]; pre[t]=i; if(!v[t]) { v[t]=true; g[t]++; if(g[t]>n) { printf("xun huan\n"); exit(0); } q.push(t); } } } } return dis[decc]!=-1e9;}double check(double k){ double tmp=0; bool ok=false; memset(front,0,sizeof(front)); tot=1; for(int i=1;i<=n;i++) add(src,i,1,0); for(int i=1;i<=n;i++) add(n+i,decc,1,0); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) add(i,j+n,1,(double)a[i][j]-k*b[i][j]); while(spfa()) { if(tmp+dis[decc]>=0) { ok=true; tmp+=dis[decc]; for(int i=pre[decc];i;i=pre[from[i]]) { flow[i]--;flow[i^1]++; } } else return false; } return ok;}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&b[i][j]); src=0,decc=n<<1|1; double l=0,r=1000000,mid; while(abs(r-l)>eps) { mid=(l+r)/2; if(check(mid)) ans=mid,l=mid+eps; else r=mid-eps; } printf("%.6lf",ans); return 0;}
[Sdoi2017]新生舞会
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。