[洛谷 4589,loj 2574][TJOI2018]智力竞赛

题目链接

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

https://loj.ac/problem/2574

题解

显然要用到二分答案,问题在于如何判定一个答案是否能达到呢?

题目的本质是用 \(n+1\) 条链覆盖图上的点,目标是让没被覆盖的点中最小权值最大化。

我们考虑建立网络流的模型。设我们的目标是覆盖权值前 \(mid\) 小的点。

首先建立超级源和超级汇 \(ss,tt\),连接 \(ss \to s\) 和 \(t \to tt\),流量为 \(n+1\),费用 \(0\)(代表 \(n+1\) 条链)。

接下来将每个点拆成入点和出点两个点,从 \(s\) 向所有入点,所有出点向 \(t\) 连流量为 \(\infty\),费用 \(0\) 的边。

对于原有的边 \(x \to y\),从 \(x\) 的出点向 \(y\) 的入点连流量 \(\infty\),费用 \(0\) 的边。

对于每个点 \(i\),从其入点向出点连两条边:一条流量,费用均为 \(1\)(如果权值不是前 \(mid\) 小则不连,以免影响答案判定),另一条流量为 \(\infty\),费用为 \(0\)(多次经过同一个点不影响结果)。

跑最大费用最大流即可,费用即为覆盖到的点数。

#include <cstring>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
struct node
{
 int id,v;
}p[505];
vector<int> e[505];
int n,m;
struct graph
{
 struct edge
 {
  int v,w,c,next;
 }e[1000005];
 struct node
 {
  int v,e;
 }p[2005];
 int head[2005],dis[2005],vis[2005];
 int s,t,cnt,minc;
 void init(int S,int T)
 {
  memset(head,0,sizeof(head));
  cnt=1,minc=0;
  s=S,t=T;
 }
 void addedge(int u,int v,int w,int 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;
  memset(dis,INF,sizeof(dis));
  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;
 }
 int mcmf()
 {
  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;
 }
}g;
bool cmp(const node&a,const node&b)
{
 return a.v<b.v;
}
bool check(int x)
{
 int maxv=p[x].v;
 int s=2*m+1,t=2*m+2;
 g.init(s,t);
 g.addedge(s,s+2,n,0),g.addedge(s+2,s,0,0);
 g.addedge(t+2,t,n,0),g.addedge(t,t+2,0,0);
 for(int i=1;i<=m;i++)
 {
  int u=p[i].id;
  g.addedge(s+2,u,INF,0),g.addedge(u,s+2,0,0);
  g.addedge(u+m,t+2,INF,0),g.addedge(t+2,u+m,0,0);
  if(p[i].v<=maxv)
   g.addedge(u,u+m,1,1),g.addedge(u+m,u,0,-1);
  g.addedge(u,u+m,INF,0),g.addedge(u+m,u,0,0);
  for(auto v:e[u])
   g.addedge(u+m,v,INF,0),g.addedge(v,u+m,0,0);
 }
 return g.mcmf()>=x;
}
int main()
{
 cin>>n>>m;
 n++;
 for(int i=1;i<=m;i++)
 {
  int k;
  cin>>p[i].v>>k;
  p[i].id=i;
  while(k--)
  {
   int x;
   cin>>x;
   e[i].push_back(x);
  }
 }
 sort(p+1,p+m+1,cmp);
 int l=1,r=m,ans=0;
 while(l<=r)
 {
  int mid=(l+r)>>1;
  if(check(mid))ans=mid,l=mid+1;
  else r=mid-1;
 }
 if(ans==m)cout<<"AK"<<endl;
 else cout<<p[ans+1].v<<endl;
 return 0;
}

发表评论

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

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据