[洛谷 4382][八省联考2018]劈配

题目链接

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

题解

Problem 1

根据题意,前 \(i\) 人最优的前提是前 \(i-1\) 人最优。

因此我们只需按名次顺序处理每一个人,处理到 \(u\) 的时候将 \(u\) 的志愿按顺序加入二分图中。每加入一个志愿就增广一次,如果存在增广路则这个人被该志愿录取。

这里存在一个优化:如果 \(u\) 不能被 \(x\) 志愿录取,可以把这个志愿对应的边全部移除(这些边的存在显然是无用的)。

为了方便起见,我们可以把前 \(i\) 个人对应的最优情况图全部存下来,这将方便我们解决第二问。

Problem 2

第二问我们可以二分答案。

设我们把 \(u\) 提升到第 \(p\) 名,则我们可以直接利用前 \(p-1\) 名的最优解,在这个基础上加入 \(u\) 的前 \(s_i\) 个志愿。如果存在增广路则说明是可以的。

#include <cstring>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
struct graph
{
 struct edge
 {
  int v,w,rev;
 };
 vector<edge> e[505];
 int cnt=1,s,t;
 int vis[505],cur[505],dis[505];
 void addedge(int u,int v,int w)
 {
  e[u].push_back({v,w,(int)e[v].size()});
  e[v].push_back({u,0,(int)e[u].size()-1});
 }
 void deledge(int u,int v)
 {
  e[u].pop_back();
  e[v].pop_back();
 }
 void init(int S,int T)
 {
  cnt=1;
  for(int i=1;i<=T;i++)
   e[i].clear();
  s=S,t=T;
 }
 bool bfs()
 {
  queue<int> q;
  memset(dis,INF,sizeof(dis));
  memset(cur,0,sizeof(cur));
  dis[s]=0,vis[s]=1;
  q.push(s);
  while(!q.empty())
  {
   int u=q.front();
   q.pop();
   for(auto ed:e[u])
    if(ed.w&&dis[ed.v]>dis[u]+1)
    {
     dis[ed.v]=dis[u]+1;
     if(!vis[ed.v])q.push(ed.v);
    }
  }
  return dis[t]!=INF;
 }
 int dfs(int u,int flow)
 {
  if(u==t)return flow;
  int siz=e[u].size(),used=0;
  for(int i=cur[u];i<siz;i++)
  {
   cur[u]=i;
   int v=e[u][i].v;
   if(dis[v]==dis[u]+1&&e[u][i].w)
   {
    int w=dfs(v,min(e[u][i].w,flow-used)),rev=e[u][i].rev;
    e[u][i].w-=w;
    e[v][rev].w+=w;
    used+=w;
    if(used==flow)break;
   }
  }
  return used;
 }
}g[205];
int n,m,s,t,b[205],p[205];
vector<int> a[205][205];
namespace pro1
{
 int res[205];
 void init()
 {
  for(int i=1;i<=n;i++)
   res[i]=m+1;
  for(int i=1;i<=m;i++)
   g[0].addedge(i+n,t,b[i]);
 }
 void solve()
 {
  init();
  int ans=0;
  for(int i=1;i<=n;i++)
  {
   g[i]=g[i-1];
   g[i].addedge(s,i,1);
   for(int j=1;j<=m;j++)
   {
    bool flag=false;
    for(auto v:a[i][j])
     g[i].addedge(i,v+n,1);
    while(g[i].bfs())
     ans+=g[i].dfs(s,INF),flag=true;
    if(!flag)
     for(auto v:a[i][j])
      g[i].deledge(i,v+n);
    else
    {
     res[i]=j;
     break;
    }
   }
  }
  for(int i=1;i<=n;i++)
   cout<<res[i]<<' ';
  cout<<endl;
 }
}
namespace pro2
{
 int res[205],vis[205];
 bool check(int x,int u)
 {
  auto G=g[x-1];
  G.addedge(s,u,1);
  for(int i=1;i<=p[u];i++)
   for(auto v:a[u][i])
    G.addedge(u,v+n,1);
  return G.bfs();
 }
 void solve()
 {
  memset(res,0,sizeof(res));
  memset(vis,0,sizeof(vis));
  for(int i=1;i<=n;i++)
  {
   if(pro1::res[i]<=p[i])
   {
    res[i]=0;
    continue;
   }
   int l=1,r=i-1;
   while(l<=r)
   {
    int mid=(l+r)>>1;
    if(check(mid,i))vis[i]=mid,l=mid+1;
    else r=mid-1;
   }
   res[i]=(vis[i]?i-vis[i]:i);
  }
  for(int i=1;i<=n;i++)
   cout<<res[i]<<' ';
  cout<<endl;
 }
}
int main()
{
 ios::sync_with_stdio(false);
 int T,c;
 cin>>T>>c;
 while(T--)
 {
  for(int i=1;i<=n;i++)
   for(int j=1;j<=m;j++)
    a[i][j].clear();
  cin>>n>>m;
  s=n+m+1,t=n+m+2;
  g[0].init(n+m+1,n+m+2);
  for(int i=1;i<=m;i++)
   cin>>b[i];
  for(int i=1;i<=n;i++)
   for(int j=1;j<=m;j++)
   {
    int x;
    cin>>x;
    if(x)a[i][x].push_back(j);
   }
  for(int i=1;i<=n;i++)
   cin>>p[i];
  pro1::solve();
  pro2::solve();
 }
 return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注