首页 > 代码库 > 【bzoj4819】[Sdoi2017]新生舞会 分数规划+费用流
【bzoj4819】[Sdoi2017]新生舞会 分数规划+费用流
题目描述
学校组织了一次新生舞会，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值最大。
输入
第一行一个整数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
输出
一行一个数，表示C的最大值。四舍五入保留6位小数，选手输出的小数需要与标准输出相等
样例输入
3
19 17 16
25 24 23
35 36 31
9 5 6
3 4 2
7 8 9
样例输出
5.357143
题解
分数规划+费用流
二分答案mid，将每个点的值看作a-b*mid。
由于每个男生只能搭配一名不同的女生，所以问题可以转化为：1个n*n的矩阵中每个位置都有1个数，求选出n个彼此不在同一行或同一列的数的和的最大值是多少。
加边s->i(1,0),i+n->t(1,0)，i->j+n(1，v[i][j])，跑最大费用最大流，若大于0则调整下界，否则调整上界，直至上下界基本重合。
证明：如果最大费用大于0，则∑(v[ik][jk])>0，即∑(a[ik][jk]-b[ik][jk]*mid)>0，即∑a[ik][jk]>∑b[ik][jk]*mid，即∑a[ik][jk]/∑b[ik][jk]＞mid，故需要调整下界来进一步更新答案，否则调整上界来调整答案。
#include <cstdio>#include <cstring>#include <queue>#define eps 1e-7using namespace std;queue<int> q;int n , head[210] , to[30000] , val[30000] , next[30000] , cnt , s , t , from[210] , pre[210];double a[110][110] , b[110][110] , cost[30000] , dis[210];void add(int x , int y , int v , double c){ to[++cnt] = y , val[cnt] = v , cost[cnt] = c , next[cnt] = head[x] , head[x] = cnt; to[++cnt] = x , val[cnt] = 0 , cost[cnt] = -c , next[cnt] = head[y] , head[y] = cnt;}bool spfa(){ int x , i; for(i = s ; i <= t ; i ++ ) from[i] = -1 , dis[i] = 10000000.0; dis[s] = 0 , q.push(s); while(!q.empty()) { x = q.front() , q.pop(); for(i = head[x] ; i ; i = next[i]) if(val[i] && dis[to[i]] > dis[x] + cost[i]) dis[to[i]] = dis[x] + cost[i] , from[to[i]] = x , pre[to[i]] = i , q.push(to[i]); } return ~from[t];}double mincost(){ int k , i; double ans = 0; while(spfa()) { k = 0x3f3f3f3f; for(i = t ; i != s ; i = from[i]) k = min(k , val[pre[i]]); ans += k * dis[t]; for(i = t ; i != s ; i = from[i]) val[pre[i]] -= k , val[pre[i] ^ 1] += k; } return ans;}bool judge(double mid){ int i , j; memset(head , 0 , sizeof(head)); cnt = 1; for(i = 1 ; i <= n ; i ++ ) add(s , i , 1 , 0); for(i = 1 ; i <= n ; i ++ ) add(i + n , t , 1 , 0); for(i = 1 ; i <= n ; i ++ ) for(j = 1 ; j <= n ; j ++ ) add(i , j + n , 1 , mid * b[i][j] - a[i][j]); return mincost() < 0;}int main(){ int i , j; double l = 0.0 , r = 10000000.0 , mid; scanf("%d" , &n); s = 0 , t = 2 * n + 1; for(i = 1 ; i <= n ; i ++ ) for(j = 1 ; j <= n ; j ++ ) scanf("%lf" , &a[i][j]); for(i = 1 ; i <= n ; i ++ ) for(j = 1 ; j <= n ; j ++ ) scanf("%lf" , &b[i][j]); while(l <= r) { mid = (l + r) / 2; if(judge(mid)) l = mid + eps; else r = mid - eps; } printf("%.6lf\n" , (l + r) / 2); return 0;}
【bzoj4819】[Sdoi2017]新生舞会 分数规划+费用流
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。