[洛谷 3705][SDOI2017]新生舞会

题目链接

https://www.luogu.com.cn/problem/P3705

题解

在二分图上套了个 0/1 分数规划的题。

容易想到二分答案 \(ans\)。接下来这样建图：

• 源点到左部点，右部点到汇点，连一条流量为 \(1\)，费用为 \(0\) 的边。
• 左部点 \(x\) 到右部点 \(y\)，连一条流量为 \(1\)，费用为 \(a_{x,y}-ans \times b_{x,y}\) 的边。

跑最大费用最大流，如果费用大于零则答案应该更大。

#include <cstring>
#include <iostream>
#include <string>
#include <queue>
#define INF 1e12
#define eqs 1e-8
using namespace std;
struct edge
{
 int v,next,w;
 double c;
}e[50005];
struct node
{
 int v,e;
}p[205];
int head[205],vis[205],a[105][105],b[105][105];
double dis[205],minc;
int n,s,t,cnt=1;
void addedge(int u,int v,int w,double c)
{
 e[++cnt].v=v;
 e[cnt].w=w;
 e[cnt].c=c;
 e[cnt].next=head[u];
 head[u]=cnt;
}
bool spfa()
{
 queue<int> q;
 for(int i=1;i<=2*n+2;i++)
  dis[i]=INF;
 dis[s]=0,vis[s]=1;
 q.push(s);
 while(!q.empty())
 {
  int u=q.front();
  q.pop();
  vis[u]=0;
  for(int i=head[u];i;i=e[i].next)
   if(e[i].w&&dis[u]-e[i].c<dis[e[i].v])
   {
    dis[e[i].v]=dis[u]-e[i].c;
    p[e[i].v].v=u;
    p[e[i].v].e=i;
    if(!vis[e[i].v])
    {
     vis[e[i].v]=1;
     q.push(e[i].v);
    }
   }
 }
 return dis[t]<INF;
}
bool check(double x)
{
 s=2*n+1,t=2*n+2;
 minc=0,cnt=1;
 memset(head,0,sizeof(head));
 for(int i=1;i<=n;i++)
 {
  addedge(s,i,1,0),addedge(i,s,0,0);
  addedge(i+n,t,1,0),addedge(t,i+n,0,0);
 }
 for(int i=1;i<=n;i++)
  for(int j=1;j<=n;j++)
  {
   double c=a[i][j]-x*b[i][j];
   addedge(i,j+n,1,c),addedge(j+n,i,0,-c);
  }
 while(spfa())
 {
  int minw=INF;
  for(int i=t;i!=s;i=p[i].v)
   minw=min(minw,e[p[i].e].w);
  for(int i=t;i!=s;i=p[i].v)
  {
   e[p[i].e].w-=minw;
   e[p[i].e^1].w+=minw;
  }
  minc-=minw*dis[t];
 }
 return minc>=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=1e8;
 while(r-l>=eqs)
 {
  double mid=(l+r)/2;
  if(check(mid))l=mid;
  else r=mid;
 }
 printf("%.6lf\n",l);
 return 0;
}