[BZOJ4819][SDOI2017]新生舞会（01分数规划+费用流）

题目：

我是超链接

题解：

也就是让求 ∑a[i][j]∑b[i][j] ∑ a [ i ] [ j ] ∑ b [ i ] [ j ] 的最大值，一眼01分数规划了，还是 ∑a−L∗∑b>0 ∑ a − L ∗ ∑ b > 0 为边权，那么现在的问题是求i,j之间有边权然后最大匹配大不大于零，如果大于0就可以更大
那么现在的问题是二分图最大匹配？
KM？能用费用流为什么用KM？
我们用最小费用最大流试试。我们把流量全为1，然后费用是 ∑a−L∗∑b ∑ a − L ∗ ∑ b 的相反数，也就是 L∗∑b−∑a L ∗ ∑ b − ∑ a ，这样跑出来最小费用流取个倒数就是最大费用。

代码：

#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#define INF 1e9
using namespace std;
const double eps=1e-8;
const int N=1005;
double dis[N],c[N*N],maxx;
int tot,nxt[N*N],point[N],v[N*N],remind[N*N],n,a[N][N],b[N][N];
bool vis[N];
void addline(int x,int y,int z,double vv)
{
++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; remind[tot]=z; c[tot]=vv;
++tot; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; remind[tot]=0; c[tot]=-vv;
}
bool spfa(int s,int t)
{
queue<int>q; q.push(s);
memset(dis,0x7f,sizeof(dis));dis[s]=0;
memset(vis,0,sizeof(vis));
while (!q.empty())
{
int now=q.front(); q.pop(); vis[now]=0;
for (int i=point[now];i!=-1;i=nxt[i])
if (dis[v[i]]>dis[now]+c[i] && remind[i])
{
dis[v[i]]=dis[now]+c[i];
if (!vis[v[i]]) vis[v[i]]=1,q.push(v[i]);
}
}
return dis[t]<INF;
}
int dfs(int now,int t,int limit)
{
vis[now]=1;
if (now==t || !limit) return limit;
int flow=0,f;
for (int i=point[now];i!=-1;i=nxt[i])
if (!vis[v[i]] && remind[i] && fabs(dis[v[i]]-dis[now]-c[i])<eps)
{
f=dfs(v[i],t,min(limit,remind[i]));
flow+=f; limit-=f;
remind[i]-=f; remind[i^1]+=f;
if (!limit) return flow;
}
return flow;
}
void zkw(int s,int t)
{
while (spfa(s,t))
{
memset(vis,0,sizeof(vis));
maxx+=dfs(s,t,INF)*dis[t];
}
}
bool check(double mid)
{
tot=-1;memset(point,-1,sizeof(point));
for (int i=1;i<=n;i++) addline(0,i,1,0),addline(i+n,2*n+1,1,0);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
addline(i,j+n,1,mid*b[i][j]-a[i][j]);
maxx=0;
zkw(0,2*n+1);maxx=-maxx;
return maxx>0;
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++) scanf("%d",&a[i][j]);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++) scanf("%d",&b[i][j]);
double l=0,r=10000;
while (r-l>eps)
{
double mid=(l+r)/2;
if (check(mid)) l=mid;
else r=mid;
}
printf("%.6lf",l);
}

最后

以上就是踏实唇膏为你收集整理的[BZOJ4819][SDOI2017]新生舞会（01分数规划+费用流）的全部内容，希望文章能够帮你解决[BZOJ4819][SDOI2017]新生舞会（01分数规划+费用流）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。