2187. 星际转移问题(最大流+分层图)「建议收藏」

全栈程序员-站长 • 2022年8月9日下午3:16 • 未分类 • 阅读 3

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

由于人类对自然资源的消耗，人们意识到大约在 2300 年之后，地球就不能再居住了。

于是在月球上建立了新的绿地，以便在需要时移民。

令人意想不到的是，2177 年冬由于未知的原因，地球环境发生了连锁崩溃，人类必须在最短的时间内迁往月球。

现有 n 个太空站（编号 1∼n）位于地球与月球之间，且有 m 艘公共交通太空船在其间来回穿梭。

每个太空站可容纳无限多的人，而每艘太空船 i 只可容纳 H[i] 个人。

每艘太空船将周期性地停靠一系列的太空站，例如：(1，3，4) 表示该太空船将周期性地停靠太空站 134134134…。

每一艘太空船从一个太空站驶往任一太空站耗时均为 1。

人们只能在太空船停靠太空站(或月球、地球)时上、下船。

初始时所有人全在地球上，太空船全在初始站，即行驶周期中的第一个站。

试设计一个算法，找出让所有人尽快地全部转移到月球上的运输方案。

输入格式
第 1 行有 3 个正整数 n（太空站个数），m（太空船个数）和 k（需要运送的地球上的人的个数）。

接下来的 m 行给出太空船的信息。第 i+1 行说明太空船 pi。第 1 个数表示 pi 可容纳的人数 H[pi]；第 2 个数表示 pi 一个周期停靠的太空站个数 r；随后 r 个数是停靠的太空站的编号 (Si1,Si2,…,Sir)，地球用 0 表示，月球用 −1 表示。

时刻 0 时，所有太空船都在初始站，然后开始运行。

在时刻 1，2，3… 等正点时刻各艘太空船停靠相应的太空站。

人只有在 0,1,2… 等正点时刻才能上下太空船。

输出格式
输出让所有人尽快地全部转移到月球上的最短用时。

如果无解，则输出 0。

数据范围
1≤n≤13,
1≤m≤20,
1≤k≤50,
1≤r≤n+2,

输入样例：
2 2 1
1 3 0 1 2
1 3 1 2 -1
输出样例：
5

#include<bits/stdc++.h>
using namespace std;
const int T = 650;
const int N = 650 * 13;
const int M = 2 * (15 * T + 25 * T + T);
const int INF = 0x3f3f3f3f;
struct Edge{ 
   
    int v,next,w;
}edge[M];
int head[N],cnt;
void add(int u,int v,int w){ 
   
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt ++;
    edge[cnt].v = u;
    edge[cnt].w = 0;
    edge[cnt].next = head[v];
    head[v] = cnt ++;
}
int n,m,s,e;
const int NUM = 22;
int h[NUM];
int port[NUM][15];
int portnum[NUM];
int maxflow = 0;
int get(int t,int a){ 
   
    return (t * (n + 2)) + a;
}
int d[N],q[N],hh = 0,tt = 0,cur[N];

bool bfs(){ 
   
    hh = tt = 0;
    memset(d,-1,sizeof d);
    d[s] = 0,q[tt ++] = s,cur[s] = head[s];
    while(hh < tt){ 
   
        int t = q[hh ++];
        for(int i = head[t];~i;i = edge[i].next){ 
   
            int v = edge[i].v,w = edge[i].w;
            if(d[v] == -1 && w){ 
   
                d[v] = d[t] + 1;
                cur[v] = head[v];
                q[tt ++] = v;
                if(v == e)return true;
            }
        }
    }
    return false;
}
int dfs(int u,int limit){ 
   
    if(u == e)return limit;
    int flow = 0;
    for(int i = cur[u];~i && flow < limit;i = edge[i].next){ 
   
        int v = edge[i].v,w = edge[i].w;
        cur[u] = i;
        if(d[v] == d[u] + 1 && w){ 
   
            int t = dfs(v,min(w,limit - flow));
            if(!t)d[v] = -1;
            flow += t,edge[i].w -= t,edge[i ^ 1].w += t; 
        }
    }
    return flow;
}
int dinic(int t){ 
   
    for(int i = 0;i <= n + 1;i ++){ 
   
        int a = get(t - 1,i),b = get(t,i);
        add(a,b,INF);
    }
    add(get(t,n + 1),e,INF);
    for(int i = 1;i <= m;i ++){ 
   
        int a = port[i][(t - 1) % portnum[i]],b = port[i][(t) % portnum[i]];
        a = get(t - 1,a),b = get(t,b);
        add(a,b,h[i]);
    }
    int flow = 0;
    while(bfs())while(flow = dfs(s,INF))maxflow += flow;
    return maxflow;
}
int main(){ 
   
    memset(head,-1,sizeof head);
    cnt = 0;
    int k;
    cin>>n>>m>>k;
    s = N - 2,e = N - 1;
    int x = 0;
    for(int i = 1;i <= m;i ++){ 
   
        cin>>h[i]>>portnum[i];
        for(int j = 0;j < portnum[i];j ++){ 
   
            cin>>x;
            if(x == -1)x = n + 1;
            port[i][j] = x;
        }
    }
    add(s,0,k);
    add(n + 1,e,INF);
    bool success = false;
    for(int i = 1;i <= T;i ++){ 
   
        if(dinic(i) == k){ 
   
            cout<<i<<endl;
            success = true;
            break;
        }
    }
    if(!success)cout<<0<<endl;
    return 0;
}