题解 P2754 【[CTSC1999]家园 / 星际转移问题】
算法：网络流（最大流）+并查集（判联通）
思路：
我们发现每一天飞船停靠的地方是不一样的，于是我们很自然佛瑞想到我们可以对每个空间站的每个时间点进行拆点（就相当于是一个动态图，每过一个时间点都可以建一个图）
总结来说就是对于这种一个点（表面意义上的一个点，比如说一个位置）对应多种情况的（比如说随着时间的推移有着不同的状态，而且这种状态>2），我们考虑在类似于分层图上面跑网络流。
接下来是建图：
首先地球是起始站，源点肯定要向每个时刻的地球连边吧，容量INF。然后月球是终点，所以要向每个时刻的月球连边，容量INF。之后对于在空间站的人们就是两种情况：
- 人们可以选择此时在该空间站的飞船，飞向下一个空间站（/地球/月球）。
- 无法移动，所以留在此处。
显然我们把时刻拆开之后，很轻易就能计算出对于每个飞船，当前时刻的位置和下一时刻的位置，直接在分层图上连边即可，容量为最大载重。因为人有可能无法移动，而且空间站的容量为无限大，所以对于每个空间站，要向下一个时刻连一条边，容量INF。
总结来说：
- 源点向每个时刻的地球连容量为INF的边
- 同理，向每个时刻的月球连容量为INF的边
- t时刻的x空间站向t+1时刻的x空间站连一条边（人们可以留在该空间站）
- 若x空间站可以到达y空间站，则从t时刻的x空间站在向t+1时刻的y空间站连一条流量为飞船流量限制的边
最后，当当前的最大流已经超过总人数时，则此时所有人都已经被运到月球，此时输出时间就好了
最后的最后，注意：
- 首先需要判断是否会有答案，即地球到太阳是否连通，在这里用并查集就可以了
- 注意n要+=2，地球和月球也算空间站
这些都理解以后就是一个板子题了!
代码附上：(dinic)
#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
const int maxm=1005;
const int INF=0x3f3f3f3f;
int n,m,k,Time,Tot,sum,tot=1,S,T=10000;
//S,T即起点，终点
int head[maxn],dep[maxn],cur[maxn],fa[maxn],num[maxn],cap[maxn],to[maxm][maxm];
//没啥好说的
vector<int> v[maxm];
queue<int> q;
struct node
{
int from,to,next;
int val;
}edge[maxn];
inline int read()
{
int s=0,f=1;
char c=getchar();
while (c<'0'||c>'9')
{
if (c=='-')
{
f=-1;
}
c=getchar();
}
while (c>='0'&&c<='9')
{
s=s*10+c-48;
c=getchar();
}
return s*f;
}
inline void add(int x,int y,int z)
{
edge[++tot].next=head[x];
edge[tot].from=x;
edge[tot].to=y;
edge[tot].val=z;
head[x]=tot;
edge[++tot].next=head[y];
edge[tot].from=y;
edge[tot].to=x;
edge[tot].val=0;
head[y]=tot;
}
//链式前向星,双向边
inline int find(int x)
{
if (fa[x]==x)
{
return x;
}
else
{
return fa[x]=find(fa[x]);
}
}
//并查集
inline void unionn(int x,int y)
{
int sx=find(x),sy=find(y);
if (sx!=sy)
{
fa[sx]=sy;
}
}
//判断连通
inline bool bfs()
{
memset(dep,-1,sizeof(dep));
memcpy(cur,head,sizeof(head));
q.push(S);
dep[S]=0;
while (!q.empty())
{
int u=q.front();
q.pop();
for (int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if (dep[v]==-1&&edge[i].val)
{
dep[v]=dep[u]+1;
q.push(v);
}
}
}
if (dep[T]==-1)
{
return false;
}
return true;
}
inline int dfs(int u,int low)
{
if (u==T)
{
return low;
}
int ret=low;
for (int i=head[u];i;i=edge[i].next)
{
int to=edge[i].to,w=edge[i].val;
if (dep[to]==dep[u]+1&&w>0)
{
int flow=dfs(to,min(ret,w));
if (flow>0)
{
edge[i].val-=flow;
edge[i^1].val+=flow;
}
ret-=flow;
if (!ret)
{
break;
}
}
}
return low-ret;
}
inline int dinic()
{
int ret=0;
while (bfs())
{
ret+=dfs(S,INF);
}
return ret;
}
//dinic板子不多说
int mian() //不要直接复制哦
{
n=read(),m=read(),k=read();
for (int i=1;i<=n+2;i++)
{
fa[i]=i;
}
for (int i=1;i<=m;i++)
{
cap[i]=read(),num[i]=read();
for (int j=1;j<=num[i];j++)
{
int p=read();
if (p==-1)
{
p=n+2;
}
else if (p==0)
{
p=n+1;
//方便一点
}
v[i].push_back(p);
if (j!=1)
{
unionn(p,v[i][v[i].size()-2]);
}
}
}
//v存的是每个飞船停留的地方
if (find(n+1)!=find(n+2))
{
cout<<"0"<<endl;
return 0;
}
n+=2;
add(S,n-1,INF);
add(n,T,INF);
while (1)
{
Time++;
//枚举每个时间段
for (int i=1;i<=m;i++)
{
int now=v[i][Time%num[i]],pre=v[i][(Time-1+num[i])%num[i]];
add(n*(Time-1)+pre,n*Time+now,cap[i]);
}
add(S,n*Time+n-1,INF);
add(Time*n+n,T,INF);
for (int j=1;j<=n;j++)
{
add((Time-1)*n+j,Time*n+j,INF);
}
//建图
sum+=dinic();
if (sum>=k)
{
cout<<Time<<endl;
break;
}
}
return 0;
}不要复制！！！后果自负qaq