luoguP3705 [SDOI2017]新生舞会
Isonan
2018-08-11 23:33:00
原题传送门[>Here<](https://www.luogu.org/problemnew/show/P3705)
我的01分数规划学习笔记[>Here<](https://www.luogu.org/blog/PopulusEuphratica/post-xue-xi-bi-ji-01-fen-shuo-gui-hua)
这道题是道比较有趣的01分数规划题,不仅需要01分数规划的思想,还要应用网络流求解,有一些复杂。
考虑对于二分出的每一个值,我们都可以网络流建图:
从源点向所有男生建边,流为1,费用为0;
从男生向女生建边,流为1,费用为$mid*b_{ij}-a_{ij}$;
从女生向汇点建边,流为1,费用为0。
接下来跑一遍最小费用最大流求出匹配的最小费用,判断是否是负数就可以了。
这题还需要卡一点常,也算是考验下应试技巧。
代码:
```cpp
#include <cstdio>
#include <cstring>
#define min(X,Y) ((X)<(Y)?(X):(Y))
int n,head[301],nxt[180001],b[180001],v[180001],k=1;
int vt[180001],flow[301],q[100001],h,t,S,T,pre[301];
double dis[301],ct[180001],bene[180001],cost[180001],a[101][101],bad[101][101],tem,l=0.0,r=100000000.0,mid;
bool inq[301];
void push(int s,int t,int val,double c){
nxt[++k]=head[s];
head[s]=k;
b[k]=t;
v[k]=val;
cost[k]=c;
}
void link(int s,int t,int val,double c){
push(s,t,val,c);
push(t,s,0,-c);
}
bool spfa(){
for(int i=S;i<=T;i++)dis[i]=1000000000.0;
h=t=0;
q[++t]=S;
inq[S]=1;
dis[S]=0.0;
flow[S]=0x7f7f7f7f;
while(h<t){
++h;inq[q[h]]=0;
for(register int i=head[q[h]];i;i=nxt[i])
if(dis[b[i]]>dis[q[h]]+cost[i]&&v[i]){
dis[b[i]]=dis[q[h]]+cost[i];
flow[b[i]]=min(flow[q[h]],v[i]);
pre[b[i]]=i;
if(!inq[b[i]])inq[b[i]]=1,q[++t]=b[i];
}
}
return dis[T]!=1000000000.0;
}
bool judge(double u){
double ans=0.0;
memset(head,0,sizeof head);
k=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
link(i,j+n,1,u*bad[i][j]-a[i][j]);
link(S,i,1,0.0);
link(i+n,T,1,0.0);
}
while(spfa()){
int tem=T;
while(tem!=S){
v[pre[tem]]-=flow[T];
v[pre[tem]^1]+=flow[T];
tem=b[pre[tem]^1];
}
ans+=(double)flow[T]*dis[T];
}
return ans<0.0;
}
int read(){
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
int main(){
n=read();
T=n+n+1;
for(register int i=1;i<=n;i++)
for(register int j=1;j<=n;j++)
a[i][j]=(double)read();
for(register int i=1;i<=n;i++)
for(register int j=1;j<=n;j++)
bad[i][j]=(double)read();
while(r-l>=0.000000001){
mid=(l+r)/2;
if(judge(mid))l=mid;
else r=mid;
}
printf("%.6lf",l);
}
```