P3705 [SDOI2017]新生舞会
题目描述
学校组织了一次新生舞会，\(Cathy\)作为经验丰富的老学姐，负责为同学们安排舞伴。
有\(n\)个男生和\(n\)个女生参加舞会买一个男生和一个女生一起跳舞，互为舞伴。
\(Cathy\)收集了这些同学之间的关系，比如两个人之前认识没计算得出\(a_{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=\frac{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}\)
输出格式：
一行一个数，表示\(C\)的最大值。四舍五入保留6位小数，选手输出的小数需要与标准输出相等。
说明
对于10%的数据， \(1≤n≤5\)
对于40%的数据， \(1≤n≤18\)
另有20%的数据， \(b_{i,j}≤1\)
对于100%的数据，\(a_{i,j},b_{i,j}<=10^4,1≤n≤100\)
做的第一道01分数规划的题。
01分数规划问题大多采用一种二分答案解法。
我们分数拆成整数，即
\(C*(b'_1+b'_2+...+b'_n)=a'_1+a'_2+...+a'_n\)
然后猜测一个\(C\)的值，检验在最优\(a,b\)配对的情况下左边与右边的大小关系，进而对\(C\)进行二分答案
如何求解最优配对呢？
再转化一下式子，左边-右边=
\(\sum_{i=1}^n (a'_i-b'_i*C)\)
我们要求解sum的最大值。
如果我们把对应点连上边\((a'_i-b'_i*C)\)，就变成了跑 最大费用最大流或者 二分图带权匹配了
最后一点，这个题它卡常...
吸氧code:
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N=204;
const int inf=0x3f3f3f3f;
const double finf=1e100;
int a[N][N],b[N][N],n,used[N],pre[N];
double l=0.0,r=0.0,dis[N];
struct node
{
double c;
int from,to,next,w;
}edge[N*N];
int head[N],cnt=-1;
void add(int u,int v,double c,int w)
{
edge[++cnt].to=v;edge[cnt].from=u;edge[cnt].w=w;edge[cnt].c=c;edge[cnt].next=head[u];head[u]=cnt;
edge[++cnt].to=u;edge[cnt].from=v;edge[cnt].w=0;edge[cnt].c=-c;edge[cnt].next=head[v];head[v]=cnt;
}
queue <int > q;
bool spfa()
{
memset(used,0,sizeof(used));
memset(pre,0,sizeof(pre));
while(!q.empty()) q.pop();
for(int i=1;i<=2*n+1;i++) dis[i]=-finf;
dis[0]=0;
pre[0]=-1;
used[0]=1;
q.push(0);
while(!q.empty())
{
int u=q.front();
q.pop();
used[u]=0;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to,w=edge[i].w;double c=edge[i].c;
if(w&&dis[u]+c>dis[v])
{
dis[v]=dis[u]+c;
pre[v]=i;
if(!used[v])
{
used[v]=1;
q.push(v);
}
}
}
}
return dis[2*n+1]!=-finf;
}
bool check(double L)
{
memset(head,-1,sizeof(head));
cnt=-1;
for(int i=1;i<=n;i++)
{
add(0,i,0,1);
add(i+n,2*n+1,0,1);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
add(i,j+n,double(a[i][j])-double(b[i][j])*L,1);
double sum=0.0;
while(spfa())
{
int now=2*n+1;
while(pre[now]!=-1)
{
edge[pre[now]].w-=1;
edge[pre[now]^1].w+=1;
sum+=edge[pre[now]].c;
now=edge[pre[now]].from;
}
}
return sum<0.0;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
r+=a[i][j];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&b[i][j]);
while(l+1e-7<r)
{
double mid=(l+r)/2.0;
if(check(mid))
r=mid;
else
l=mid;
}
printf("%lf\n",l);
return 0;
}
2018.6.4