目录
显示
题目链接
https://www.luogu.com.cn/problem/P2754
题解
在分层图上跑最大流。
我们设 \((x,y)\) 表示 \(x\) 时刻的 \(y\) 太空站这一状态。
则可以这样建图：
- 源点向所有 \((x,0)\) 连流量为 \(\infty\) 的边；
- 所有 \((x,y)\) 向 \((x+1,y)\) 连流量为 \(\infty\) 的边（人可以在当前太空站停留）；
- 如果 \(x\) 时刻可以从 \(u\) 到达 \(v\)，则从 \((x,u)\) 向 \((x+1,v)\) 连流量为载客人数上限的边；
- 所有 \((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;
}