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 系列题目:
近期评论