【BZOJ4819】新生舞会（01分数规划,费用流）

分手后的思念是犯贱 2022-01-09 07:21 223阅读 0赞

## Solution ##

考虑一下这个东西的模型转换：

\\(\\frac\{\\sum\_\{i=1\}^n\{a\_i\}\}\{\\sum\_\{i=1\}^n\{b\_i\}\}\\)

然后转换一下发现显然是01分数规划。

\\(\\sum\_\{i=1\}^n\{b\_i\}\*mid\\leq \\sum\_\{i=1\}^n\{a\_i\}\\)

然后再移项：

\\(0 \\leq \\sum\_\{i=1\}^n\{a\_i-b\_i\*mid\}\\)

然后就是求一个最大费用最大流判断是不是>0就好了。

口胡简单，实现靠自己

## 代码实现 ##

#include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #include<algorithm> #include<queue> #include<set> #include<map> #include<iostream> using namespace std; #define ll long long #define re register #define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout) inline int gi() { int f=1,sum=0;char ch=getchar(); while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();} return f*sum; } const int N=210; const double eps=1e-10,Inf=1e18; int front[N],to[(N*N)<<2],nxt[(N*N)<<2],w[(N*N)<<2],s=0,t,cnt,vis[N<<2],fa[N<<2],pre[N<<2],n,a[N][N],b[N][N]; double c[(N*N)<<2],dis[N<<2]; void Add(int u,int v,int val,double f){ to[cnt]=v;nxt[cnt]=front[u];front[u]=cnt;w[cnt]=val;c[cnt++]=f; to[cnt]=u;nxt[cnt]=front[v];front[v]=cnt;w[cnt]=0;c[cnt++]=-f; } queue<int>Q; bool SPFA(){ for(int i=s;i<=t+1;i++)dis[i]=-Inf; dis[s]=0; Q.push(s); while(!Q.empty()){ int u=Q.front();Q.pop();vis[u]=0; for(int i=front[u];i!=-1;i=nxt[i]){ int v=to[i]; if(w[i] && dis[v]<dis[u]+c[i]){ dis[v]=dis[u]+c[i];fa[v]=u;pre[v]=i; if(!vis[v]){ vis[v]=1;Q.push(v); } } } } return dis[t]!=dis[t+1]; } double McMf(){ double ans=0; while(SPFA()){ ans+=dis[t]; for(int i=t;i!=s;i=fa[i]){ w[pre[i]]--;w[pre[i]^1]++; } } return ans; } bool check(double mid){ memset(front,-1,sizeof(front));cnt=0; for(int i=1;i<=n;i++){ Add(s,i,1,0);Add(i+n,t,1,0); } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) Add(i,j+n,1,(double)a[i][j]-b[i][j]*mid); if(McMf()>=0)return true; return false; } int main() { n=gi();t=n+n+1; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=gi(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) b[i][j]=gi(); double l=0,r=10000; while(r-l>eps){ double mid=l+(r-l)*0.5; if(check(mid))l=mid; else r=mid; } printf("%.6lf\n",l); return 0; }

转载于:https://www.cnblogs.com/mle-world/p/10302001.html