SDOI2017 Round 1 Day 2 T1，一道 二分答案 + 网络流 的题目（0/1 分数规划）。
题目链接：Luogu P3705/LibreOJ 2003/BZOJ 4819/SDOI2017 R1D2T1。
题目
题目描述
学校组织了一次新生舞会，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^\text{‘} _ 1,a^\text{‘} _ 2,\cdots,a^\text{‘} _ n\)，假设每对舞伴不协调程度分别是 \(b^\text{‘} _ 1,b^\text{‘} _ 2,\cdots,b^\text{‘} _ n\)。令
\[C=\frac{a^\text{‘} _ 1+a^\text{‘} _ 2+\cdots+a^\text{‘} _ n}{b^\text{‘} _ 1+b^\text{‘} _ 2+\cdots+b^\text{‘} _ n}\]
Cathy 希望 \(C\) 值最大。
数据范围
对于 \(10\%\) 的数据，\(1\leq n\leq 5\)；
对于 \(40\%\) 的数据，\(1\leq n\leq 18\)；
另外存在 \(20\%\) 的数据，\(b _ {i,j}=1\)；
对于 \(100\%\) 的数据，\(1\leq n\leq 100,1\leq a _ {i,j},b _ {i,j}\leq 10^4\)。
时空限制
| 题目编号 | 时间限制 | 空间限制 |
| Luogu P3705 | \(1.5\text{s}\) | \(250\text{MiB}\) |
| LibreOJ 2003 | \(1.5\text{s}\) | \(256\text{MiB}\) |
| BZOJ 4819 | \(10\text{s}\) | \(128\text{MiB}\) |
| SDOI2017 R1D2T1。 | \(1.5\text{s}\) | \(256\text{MiB}\) |
题解
思路
显然是 \(0/1\) 分数规划问题，考虑二分 \(C\)。
那么判断条件改为
\[\sum^n _ {i=1}a _ i-C\times b _ i=0\]
跑费用流即可。
代码
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define INF 0X3F3F3F3F
#define eps 1e-8
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
reg char ch=getchar();
reg int res=0;
while(ch<'0'||'9'<ch)ch=getchar();
while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
return res;
}
const int MAXN=100+5;
const int MAXV=MAXN*2+5;
const int MAXE=(MAXN*MAXN+MAXN*2)*2;
int n;
int a[MAXN][MAXN];
int b[MAXN][MAXN];
int cnt,head[MAXV],to[MAXE],w[MAXE],Next[MAXE];
double p[MAXE];
inline void Add_Edge(reg int u,reg int v,reg int len,reg double val){
Next[++cnt]=head[u];
to[cnt]=v;
w[cnt]=len;
p[cnt]=val;
head[u]=cnt;
return;
}
inline void Add_Tube(reg int u,reg int v,reg int len,reg double val){
Add_Edge(u,v,len,val);
Add_Edge(v,u,0,-val);
return;
}
bool inque[MAXV];
double dis[MAXV];
queue<int> Q;
inline bool SPFA(int s,reg int t){
for(reg int i=s;i<=t;++i)
dis[i]=-INF;
inque[s]=true,dis[s]=0,Q.push(s);
while(!Q.empty()){
reg int id=Q.front();
Q.pop();
inque[id]=false;
for(reg int i=head[id];i;i=Next[i]){
int v=to[i];
if(dis[v]<dis[id]+p[i]&&w[i]){
dis[v]=dis[id]+p[i];
if(!inque[v]){
inque[v]=true;
Q.push(v);
}
}
}
}
return fabs(dis[t]+INF)>eps;
}
bool vis[MAXV];
int cur[MAXV];
double MaxCost;
inline int DFS(reg int u,reg int t,reg int lim){
if(u==t){
MaxCost+=dis[t]*lim;
return lim;
}
vis[u]=true;
reg int flow=0;
for(reg int &i=cur[u];i;i=Next[i]){
reg int v=to[i];
if(dis[v]==dis[u]+p[i]&&w[i]&&!vis[v]){
reg int f=DFS(v,t,min(lim-flow,w[i]));
if(f){
flow+=f;
w[i]-=f;
w[i^1]+=f;
if(flow==lim)
break;
}
}
}
vis[u]=false;
return flow;
}
inline int Dinic(reg int s,reg int t){
reg int res=0;
MaxCost=0;
while(SPFA(s,t)){
memcpy(cur,head,sizeof(head));
res+=DFS(s,t,INF);
}
return res;
}
inline bool check(reg double C){
cnt=1,memset(head,0,sizeof(head));
reg int s=0,t=2*n+1;
for(reg int i=1;i<=n;++i){
Add_Tube(s,i,1,0.0);
Add_Tube(i+n,t,1,0.0);
for(reg int j=1;j<=n;++j)
Add_Tube(i,j+n,1,a[i][j]-b[i][j]*C);
}
Dinic(s,t);
return MaxCost>=0;
}
int main(void){
n=read();
for(reg int i=1;i<=n;++i)
for(reg int j=1;j<=n;++j)
a[i][j]=read();
for(reg int i=1;i<=n;++i)
for(reg int j=1;j<=n;++j)
b[i][j]=read();
reg double l=0,r=1e5,mid;
while(fabs(r-l)>eps){
mid=(l+r)*0.5;
if(check(mid)){
l=mid;
}
else
r=mid;
}
printf("%.6lf\n",l);
return 0;
}
相关题目
SDOI2017 系列题目：
近期评论