「SDOI2017」新生舞会 - 分数规划+二分图最大权匹配 | Bill Yang's Blog

「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,\ldots,a’_n$,假设每对舞伴的不协调程度分别是$b’_1,b’_2,\ldots,b’_n$。令$C=\frac{a’_1+a’_2+\ldots+a’_n}{b’_1+b’_2+\ldots+b’_n}$,Cathy希望$C$值最大。


题目分析

答案是分数形式,不难想到分数规划。

则:

因此二分$\lambda$将$a’_i-\lambda b’_i$作为权值进行最大权匹配,若答案$\gt0$说明$\lambda$较小,反之说明$\lambda$较大。

因为是实数费用,用zkw费用流会被卡,于是写了EK。
用KM的就不提了。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=205;
const double eps=1e-8;

int dcmp(double x) {
if(fabs(x)<=eps)return 0;
if(x>eps)return 1;
return -1;
}

struct Edge {
int from,to,cap,flow;
double cost;
Edge(int x=0,int y=0,int c=0,int f=0,double co=0):from(x),to(y),cap(c),flow(f),cost(co) {}
};

struct MinimumCost_MaximumFlow { //EK Edition
int n,m;
vector<Edge>edges;
vector<int>G[maxn];
bool inque[maxn];
int a[maxn],path[maxn];
double dist[maxn];
void init(int n) {
this->n=n;
edges.clear();
for(int i=1; i<=n; i++)G[i].clear();
}
void AddEdge(int x,int y,int v,double f) {
edges.push_back(Edge(x,y,v,0,f));
edges.push_back(Edge(y,x,0,0,-f));
m=edges.size();
G[x].push_back(m-2);
G[y].push_back(m-1);
}
bool bellmanford(int s,int t,int& flow,double& cost) {
for(int i=1; i<=n; i++)dist[i]=-1e18;
memset(inque,0,sizeof(inque));
queue<int>Q;
Q.push(s);
dist[s]=path[s]=0;
a[s]=INT_MAX;
while(!Q.empty()) {
int Now=Q.front();
Q.pop();
inque[Now]=0;
for(int id:G[Now]) {
Edge& e=edges[id];
int Next=e.to;
if(e.cap>e.flow&&dcmp(dist[Next]-dist[Now]-e.cost)<0) {
dist[Next]=dist[Now]+e.cost;
path[Next]=id;
a[Next]=min(a[Now],e.cap-e.flow);
if(!inque[Next]) {
Q.push(Next);
inque[Next]=1;
}
}
}
}
if(dist[t]==-1e18)return false;
flow+=a[t];
cost+=dist[t]*a[t];
for(int Now=t; Now!=s; Now=edges[path[Now]].from) {
edges[path[Now]].flow+=a[t];
edges[path[Now]^1].flow-=a[t];
}
return true;
}
int maxflow(int s,int t,double& cost) {
int flow=0;
cost=0;
while(bellmanford(s,t,flow,cost));
return flow;
}
} mcmf;

int n;
double a[105][105],b[105][105];

bool Check(double x) {
int S=2*n+1,T=2*n+2;
mcmf.init(T);
for(int i=1; i<=n; i++) {
mcmf.AddEdge(S,i,1,0);
mcmf.AddEdge(n+i,T,1,0);
}
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
mcmf.AddEdge(i,n+j,1,a[i][j]-b[i][j]*x);
double cost=0;
mcmf.maxflow(S,T,cost);
return cost>eps;
}

int main() {
n=Get_Int();
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
a[i][j]=Get_Int();
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
b[i][j]=Get_Int();
double Left=0,Right=1e6;
while(Right-Left>eps) {
double mid=(Left+Right)/2;
if(Check(mid))Left=mid;
else Right=mid;
}
printf("%0.6lf\n",Right);
return 0;
}
姥爷们赏瓶冰阔落吧~
0%