P3705 [SDOI2017]新生舞会
斯德哥尔摩
2018-05-29 23:16:04
[P3705 [SDOI2017]新生舞会](https://www.luogu.org/problemnew/show/P3705)
刚拿道题，10%直接暴力dfs；
40%知道是状压DP，然而不会写，尴尬。。。
还有20%裸的最大费用最大流；
然而正解是个非常奇怪的算法——**01分数规划**
我也是第一次听说这个算法，我也是一脸的懵逼。。。
01分数规划是这样的一类问题：
有$n$物品，每一个物品有一个收益$a_i$，一个代价$b_i$，我们要求一个方案使得$$\frac{\sum_{i=1}^{n}a_i}{\sum_{i=1}^{n}b_i}$$最大。
而这种问题一般都与**二分答案**在一起。
而$$\frac{\sum_{i=1}^{n}a_i}{\sum_{i=1}^{n}b_i}>=ans$$就是$$\sum_{i=1}^{n}a_i-ans\sum_{i=1}^{n}b_i>=0$$
所以我们可以二分一个值，得出一个更优的解，并且在这个解的基础上继续做，直到满足精度。
至于怎样求这个解，就丢给了最大费用最大流。
建图相对简单：
源点$S$连向所有男生，流量为1，费用为0；
所有女生连向汇点$T$，流量为1，费用为0；
第$i$个男生与第$j$个女生连边流量为1，费用为$a_{i,j}-ans* b_{i,j}$。
建图完成后，如果最大费用最大流大于等于$0$ ，那么$C>=ans$。
注意：
1. 记得将二分边界调好，这是实数二分，弄不好就$TLE$了。
2. 此题卡常！此题卡常！此题卡常！记得开一下$O2$，不然会$TLE$得很惨。。。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
#define MAXN 210
#define MAX 999999999
#define eps (1e-7)
using namespace std;
int n,m,s,t,c;
int A[MAXN][MAXN],B[MAXN][MAXN],head[MAXN],deep[MAXN],fa[MAXN],flow[MAXN];
double maxflow,mincost,path[MAXN];
bool vis[MAXN];
struct node{
int next,to,w;
double cost;
}a[MAXN*MAXN<<1];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
inline int relax(int u,int v,int i,int w,double cost){
if(path[v]>path[u]+cost){
path[v]=path[u]+cost;
fa[v]=u;
deep[v]=i;
flow[v]=min(flow[u],w);
return 1;
}
return 0;
}
inline void add(int u,int v,int w,double cost){
a[c].to=v;a[c].w=w;a[c].cost=cost;a[c].next=head[u];head[u]=c++;
a[c].to=u;a[c].w=0;a[c].cost=-cost;a[c].next=head[v];head[v]=c++;
}
bool spfa(){
int u,v;
queue<int> q;
for(int i=s;i<=t;i++){path[i]=MAX;vis[i]=false;fa[i]=-1;}
path[s]=0;
vis[s]=true;
fa[s]=0;
flow[s]=MAX;
q.push(s);
while(!q.empty()){
u=q.front();
q.pop();
vis[u]=false;
for(int i=head[u];i;i=a[i].next){
v=a[i].to;
if(a[i].w&&relax(u,v,i,a[i].w,a[i].cost)&&!vis[v]){
vis[v]=true;
q.push(v);
}
}
}
if(path[t]==MAX)return false;
return true;
}
void EK(){
while(spfa()){
for(int i=t;i!=s;i=fa[i]){
a[deep[i]].w-=flow[t];
a[deep[i]^1].w+=flow[t];
}
maxflow+=flow[t];
mincost+=(double)path[t]*flow[t];
}
}
double solve(double x){
c=2;
memset(head,0,sizeof(head));
maxflow=mincost=0;
for(int i=1;i<=n;i++){
add(s,i,1,0);
add(i+n,t,1,0);
for(int j=1;j<=n;j++)
add(i,j+n,1,(double)x*B[i][j]-A[i][j]);//最大费用最大流，转成负边跑最小费用最大流
}
EK();
return -mincost;//最后添个负号
}
void work(){
double l=0,r=1000000,mid;
while(r-l>eps){//实数二分
mid=(l+r)/2.00;
double s=solve(mid);
if(s>=0)l=mid;
else r=mid;
}
printf("%.6lf\n",l);
}
void init(){
int u,v,w,cost;
n=read();
s=0;t=(n<<1)+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
A[i][j]=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
B[i][j]=read();
}
int main(){
init();
work();
return 0;
}
```