2187. 星际转移问题

2187. 星际转移问题
至少时间问题，这里面没有路程的概念，所以采用分层图，一步步走点。
可以直接在上一次的残图上进行走点，这样子复杂度会低很多

#include <bits/stdc++.h>
using namespace std;
const int N=5e4+5,M=1e6+5;
const int inf=1e9;

int h[N],ne[M],e[M],w[M],tot=1;
void add(int from,int to,int wi) {
    e[++tot]=to;
    w[tot]=wi;
    ne[tot]=h[from];
    h[from]=tot;
}

int S=N-2,T=N-1;
int cur[N],dep[N];
bool bfs() {
    memcpy(cur,h,sizeof(h));
    memset(dep,0,sizeof(dep));
    queue<int>q;
    q.push(S);
    dep[S]=1;
    while(!q.empty()) {
        int now=q.front();
        q.pop();
        for(int i=h[now];i;i=ne[i]) {
            int to=e[i];
            if(w[i]>0&&dep[to]==0)
                dep[to]=dep[now]+1,q.push(to);
        }
    }
    return dep[T];
}

int dfs(int now,int sum) {
    if(now==T)return sum;
    int ans=0;
    for(int i=cur[now];i&&sum;i=ne[i]) {
        cur[now]=i;
        int to=e[i];
        if(dep[to]==dep[now]+1&&w[i]>0) {
            int k=dfs(to,min(sum,w[i]));
            w[i]-=k;
            w[i^1]+=k;
            sum-=k;
            ans+=k;
        }
    }
    return ans;
}

int dinic() {
    int ans=0;
    while(bfs())ans+=dfs(S,inf);
    return ans;
}

int fa[N];
int find(int x) {
    return x==fa[x]?fa[x]:fa[x]=find(fa[x]);
}

struct node {
    int w,siz,v[30];
}a[30];
int n,m,k;
int get(int a,int b) {
    return (n+2)*b+a;
}

int main() {
    
    cin>>n>>m>>k;
    for(int i=0;i<=n+1;i++)fa[i]=i;
    for(int i=1;i<=m;i++) {
        cin>>a[i].w>>a[i].siz;
        for(int j=0;j<a[i].siz;j++) {
            int x;cin>>x;
            if(x==-1)x=n+1;
            a[i].v[j]=x;
            if(j)fa[find(a[i].v[j-1])]=find(a[i].v[j]);
        }
    }
    if(find(0)!=find(n+1))cout<<"0\n";
    else {
        add(S,get(0,0),k);
        add(get(0,0),S,0);
        add(get(n+1,0),T,inf);
        add(T,get(n+1,0),0);
        int ans=1,sum=0;
        while(1) {
            add(get(n+1,ans),T,inf);
            add(T,get(n+1,ans),0);
            for(int i=0;i<=n+1;i++) {
                add(get(i,ans-1),get(i,ans),inf);
                add(get(i,ans),get(i,ans-1),0);
            }
            for(int i=1;i<=m;i++) {
                int cnt=a[i].siz;
                int x=a[i].v[(ans-1+cnt)%cnt],y=a[i].v[ans%cnt];
                add(get(x,ans-1),get(y,ans),a[i].w);
                add(get(y,ans),get(x,ans-1),0);
            }
            sum+=dinic();
            if(sum>=k)break;
            ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}