简单解题思路

问题描述

给定一个星际运输网络（无向图），有 n 个星球（节点），m 条航线（边），k 艘飞船，起点 s 和终点 t。飞船每天可以沿航线移动一次，求：

1. 最少需要多少天，才能让所有 k 艘飞船从 s 到达 t？
2. 每天的飞船移动方案（输出每艘飞船的移动路径）。

核心思路

1. 时间分层网络流：

   • 将时间拆分成多个“天”，每天复制一份完整的星际网络。
   • 飞船每天只能移动一步，因此需要逐天扩展网络，直到所有飞船到达 t。

2. 最大流算法（Dinic）：

   • 每天增加一层网络，计算当前能运送多少飞船（最大流）。
   • 累计运送的飞船数，直到达到 k 艘。

3. 路径追踪：

   • 根据残余网络（flow 值）反向追踪每艘飞船的移动路径。
   • 记录每天每艘飞船的位置变化。

关键步骤

1. 输入：

   • 读取 n（星球数）、m（航线数）、k（飞船数）、s（起点）、t（终点）。
   • 读取所有航线（边）。

2. 时间扩展 & 最大流计算：

   • 每天新增一层网络（Build(days)），连接前一天的星球到当前天的星球。
   • 用 Dinic 算法计算当前能运送的飞船数 maxflow(k - f)，累计到 f。
   • 重复直到 f >= k，输出最少天数 days。

3. 输出飞船路径：

   • 遍历每天的残余网络，检查哪些飞船移动了。
   • 记录每艘飞船的移动位置，并输出。

示例

• 输入：

  3 3 2 1 3
  1 2
  2 3
  1 3
  

• 输出：

  2       // 最少需要 2 天
  1 1 2   // 第 1 天：飞船 1 从 1 移动到 2
  1 1 3   // 第 2 天：飞船 1 从 2 移动到 3
  

总结

• 核心算法：时间分层 + 最大流（Dinic）。
• 关键优化：逐天扩展网络，避免一次性建图。
• 输出处理：通过残余网络反向追踪飞船路径。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
const int inf=1<<30;
const int maxn=5e3;
const int maxm=1e5;
const int maxe=210;
struct Edge
{
    int from;
    int to;
}E[maxe];
struct Ship
{
    int pos;
    bool isupdate;
    bool islive;
    Ship(){};
    Ship(int spos)
    {
        pos=spos;
        isupdate=true;
        islive=true;
    }
}ship[55];
int n,m,k,s,t,st,des,e,head[maxn],pnt[maxm],nxt[maxm],flow[maxm],level[maxn];
queue<int> q;
void AddEdge(int u,int v,int f)
{
    pnt[e]=v;nxt[e]=head[u];flow[e]=f;head[u]=e++;
    pnt[e]=u;nxt[e]=head[v];flow[e]=0;head[v]=e++;
}
int GetPoint(int val)
{
    val%=n;
    if(!val)
        return n;
    return val;
}
bool BFS()
{
    memset(level,0,sizeof(level));
    level[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i!=-1;i=nxt[i])
            if(flow[i]&&!level[pnt[i]])
            {
                level[pnt[i]]=level[u]+1;
                q.push(pnt[i]);
            }
    }
    return level[des];
}
int DFS(int u,int maxf)
{
    if(u==des||!maxf)
        return maxf;
    for(int i=head[u],t;i!=-1;i=nxt[i])
        if(level[pnt[i]]==level[u]+1&&(t=DFS(pnt[i],min(flow[i],maxf))))
        {
            flow[i]-=t;
            flow[i^1]+=t;
            return t;
        }
    return level[u]=0;
}
int maxflow(int flow)
{
    int ans=0;
    while(BFS())
        while(1)
        {
            int val=DFS(s,flow-ans);
            ans+=val;
            if(!val)
                break;
            if(flow==ans)
                return ans;
        }
    return ans;
}
void Build(int days)
{
    for(int i=0;i<m;i++)
    {
        AddEdge(E[i].from+n*(days-1),E[i].to+n*days,1);
        AddEdge(E[i].to+n*(days-1),E[i].from+n*days,1);
    }
    for(int i=1;i<=n;i++)
        AddEdge(i+n*(days-1),i+n*days,inf);
}
int main()
{
    while(scanf("%d%d%d%d%d",&n,&m,&k,&s,&t)!=EOF)
    {
        e=0;
        memset(head,-1,sizeof(head));
        for(int i=0;i<m;i++)
            scanf("%d%d",&E[i].from,&E[i].to);
        int days=0,f=0;
        while(1)
        {
            Build(++days);
            des=n*days+t;
            f+=maxflow(k-f);
            if(f>=k)
                break;
        }
        printf("%d\n",days);
        int index=0,ex=0,id=1,ans[51];
        for(int i=1;i<=days;i++)
        {
            int cnt=0;
            memset(ans,0,sizeof(ans));
            for(int j=0;j<m;j++)
            {
                int f1=flow[ex];ex+=2;
                int f2=flow[ex];ex+=2;
                int u=-1,v=-1;
                if(f1==0&&f2==1)
                {
                    u=E[j].from;
                    v=E[j].to;
                }
                if(f1==1&&f2==0)
                {
                    u=E[j].to;
                    v=E[j].from;
                }
                if(u==-1)
                    continue;
                if(u==s)
                {
                    ship[++index]=Ship(v);
                    ans[index]=v;
                    cnt++;
                }
                else
                {
                    for(int l=1;l<=index;l++)
                        if(ship[l].pos==u&&ship[l].islive&&!ship[l].isupdate)
                        {
                            ship[l].pos=v;
                            ship[l].isupdate=true;
                            ans[l]=v;
                            cnt++;
                            if(v==t)
                                ship[l].islive=false;
                            break;
                        }
                }
            }
            ex+=2*n;
            printf("%d",cnt);
            for(int j=1;j<=index;j++)
            {
               if(ans[j])
                  printf(" %d %d",j,ans[j]); 
                ship[j].isupdate=false;
            }
            printf("\n");
        }
    }
    return 0;
}