[洛谷 2754][CTSC1999]家园 / 星际转移问题

题目链接

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

题解

在分层图上跑最大流。

我们设 \((x,y)\) 表示 \(x\) 时刻的 \(y\) 太空站这一状态。

则可以这样建图:

  1. 源点向所有 \((x,0)\) 连流量为 \(\infty\) 的边;
  2. 所有 \((x,y)\) 向 \((x+1,y)\) 连流量为 \(\infty\) 的边(人可以在当前太空站停留);
  3. 如果 \(x\) 时刻可以从 \(u\) 到达 \(v\),则从 \((x,u)\) 向 \((x+1,v)\) 连流量为载客人数上限的边;
  4. 所有 \((x,-1)\) 向汇点连流量为 \(\infty\) 的边。

先用并查集判断连通性,如果地球和月球不连接则无解。

否则枚举时间 \(t\),\(t\) 每增加 \(1\),就按照上面的方法新建一组点和对应的边。

在原来的残量网络上跑最大流,直到最大流大于等于 \(k\) 结束循环。

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#define INF 0x3f3f3f3f
using namespace std;
struct edge
{
 int v,w,next;
}e[1000005];
struct ship
{
 int h,r;
 vector<int> s;
}a[25];
struct dsu
{
 int fa[25];
 void init(int x)
 {
  for(int i=1;i<=x;i++)
   fa[i]=i;
 }
 int find(int x)
 {
  return fa[x]==x?x:fa[x]=find(fa[x]);
 }
 void unionn(int x,int y)
 {
  fa[y]=x;
 }
}d;
int s=100000,t=100001,cnt=1;
int head[100005],dep[100005],vis[100005],cur[100005];
int id[25],lid[25];
void addedge(int u,int v,int w)
{
 e[++cnt].v=v;
 e[cnt].w=w;
 e[cnt].next=head[u];
 head[u]=cnt;
}
bool bfs()
{
 queue<int> q;
 memset(dep,INF,sizeof(dep));
 memset(vis,0,sizeof(vis));
 memcpy(cur,head,sizeof(head));
 dep[s]=0;
 vis[s]=1;
 q.push(s);
 while(!q.empty())
 {
  int p=q.front();
  q.pop();
  vis[p]=0;
  for(int i=head[p];i;i=e[i].next)
   if(dep[e[i].v]>dep[p]+1&&e[i].w)
   {
    dep[e[i].v]=dep[p]+1;
    if(!vis[e[i].v])
    {
     vis[e[i].v]=1;
     q.push(e[i].v);
    }
   }
 }
 if(dep[t]==INF)return 0;
 return 1;
}
int dfs(int p,int w)
{
 if(p==t)return w;
 int used=0;
 for(int i=cur[p];i;i=e[i].next)
 {
  cur[p]=i;
  if(dep[e[i].v]==dep[p]+1&&e[i].w)
  {
   int flow=dfs(e[i].v,min(w-used,e[i].w));
   if(flow)
   {
    used+=flow;
    e[i].w-=flow;
    e[i^1].w+=flow;
    if(used==w)break;
   }
  }
 }
 return used;
}
int main()
{
 int n,m,k;
 cin>>n>>m>>k;
 d.init(n+2);
 for(int i=1;i<=m;i++)
 {
  cin>>a[i].h>>a[i].r;
  int last=0;
  for(int j=1;j<=a[i].r;j++)
  {
   int x;
   cin>>x;
   if(x==0)x=n+1;
   if(x==-1)x=n+2;
   if(j==1)last=x;
   else d.unionn(d.find(last),d.find(x)),last=x;
   a[i].s.push_back(x);
  }
 }
 if(d.find(n+1)!=d.find(n+2))cout<<0<<endl;
 else
 {
  int ans=0,tot=0;
  for(int i=1;i<=n+2;i++)
  {
   lid[i]=++tot;
   if(i==n+1)
    addedge(s,tot,INF),addedge(tot,s,0);
   if(i==n+2)
    addedge(tot,t,INF),addedge(t,tot,0);
  }
  do
  {
   ans++;
   for(int i=1;i<=n+2;i++)
   {
    id[i]=++tot;
    addedge(lid[i],id[i],INF),addedge(id[i],lid[i],0);
    if(i==n+1)
     addedge(s,tot,INF),addedge(tot,s,0);
    if(i==n+2)
     addedge(tot,t,INF),addedge(t,tot,0);
   }
   for(int i=1;i<=m;i++)
   {
    int t=ans%a[i].r;
    int u=(t==0?a[i].s[a[i].r-1]:a[i].s[t-1]),v=a[i].s[t];
    addedge(lid[u],id[v],a[i].h),addedge(id[v],lid[u],0);
   }
   while(bfs())
    k-=dfs(s,INF);
   memcpy(lid,id,sizeof(id));
  }while(k>0);
  cout<<ans<<endl;
 }
 return 0;
}

发表评论

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

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