判断有没有解可以通过并查集快速判断起点和终点是否联通,如果联通则说明有解,反之则说明无解

因为网络流中没有”距离”的概念,所以我们采用了分层图的形式

建图方法:

将每个点按照时间进行拆点,将每个点拆成day个不同的点(假设day是最终的答案)

然后可以用一个(i,k)的二元组来表示每一个点(表示第i号点第k天的状态)

源点先向第0天的地球连一条容量为正无穷的边

第0天的月球向汇点连一条容量为正无穷的边

对于之后的每一天

月球向终点连一天正无穷的边(到达月球等于到达了终点)

每个点的前一天的状态向每个点当天的状态连一条正无穷的边(因为每个乘客都可以选择在当前点过夜)

每辆车前一天的停靠站向当天的停靠站连一条容量为当前车的容量的边(因为只能做这么多人)

#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

const int N=1300;
const int M=4000;
const int INF=1e9;

int n,m,k,S,T,idx;
int h[N],e[M],ne[M],f[M];
int cur[N],q[N],dist[N],p[N];

struct Ship{
    int id,c,cnt;
    int path[30];
}ship[30];

int find(int u){
    if(u!=p[u]) p[u]=find(p[u]);
    return p[u];
}

//因为包括地球和月球,所以总共n+2个点
int get(int i,int day){
    return day*(n+2)+i;
}

void add(int a,int b,int c){
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[a],h[a]=idx++;
}

bool bfs(){
    memset(dist,-1,sizeof(dist));
    int tt=0,hh=0;
    q[tt++]=S;
    dist[S]=0;
    cur[S]=h[S];

    while(tt!=hh){
        int t=q[hh++];
        if(hh==N) hh=0;

        for(int i=h[t];i!=-1;i=ne[i]){
            int ver=e[i];
            if(dist[ver]==-1&&f[i]){
                dist[ver]=dist[t]+1;
                cur[ver]=h[ver];
                if(ver==T) return true;
                q[tt++]=ver;
                if(tt==N) tt=0;
            }
        }
    }
    return false;
}

int find(int u,int limit){
    if(u==T) return limit;

    int flow=0;
    for(int i=cur[u];i!=-1&&flow<limit;i=ne[i]){
        cur[u]=i;
        int ver=e[i];
        if(dist[ver]==dist[u]+1&&f[i]){
            int t=find(ver,min(f[i],limit-flow));
            if(!t) dist[ver]=-1;
            f[i]-=t;
            f[i^1]+=t;
            flow+=t;
        }
    }
    return flow;
}

int dinic(){
    int maxflow=0;
    while(bfs()){
        int flow=0;
        while(flow=find(S,INF)) maxflow+=flow;
    }
    return maxflow;
}


//0表示地球,n+1表示月球
int main(){
    cin>>n>>m>>k;
    S=N-2,T=N-1;

    memset(h,-1,sizeof(h));
    for(int i=0;i<=n+1;++i) p[i]=i;

    for(int i=0;i<m;++i){
        int c,cnt;
        cin>>c>>cnt;
        ship[i].id=i;
        ship[i].cnt=cnt;
        ship[i].c=c;
        for(int j=0;j<cnt;++j){
            int pos;
            cin>>pos;
            if(pos==-1) pos=n+1;
            ship[i].path[j]=pos;
            if(j){
                int a=ship[i].path[j-1];
                int b=ship[i].path[j];
                a=find(a);
                b=find(b);
                p[a]=b;
            }
        }
    }
    //不联通说明无解
    if(find(0)!=find(n+1)) puts("0");
    else{
        add(S,get(0,0),INF);
        add(get(n+1,0),T,INF);
        int day=1;
        int res=0;
        while(1){
            //新的一天
            //月球向T连一条正无穷的边
            add(get(n+1,day),T,INF);
            //每个点前一天向当天连一条正无穷的边
            for(int i=0;i<=n+1;++i) add(get(i,day-1),get(i,day),INF);
            //每辆车前一天的位置向当天的位置连一条容量等于车的容量的边
            for(int i=0;i<m;++i){
                int cnt=ship[i].cnt;
                int a=ship[i].path[(day-1)%cnt];
                int b=ship[i].path[day%cnt];
                int c=ship[i].c;
                add(get(a,day-1),get(b,day),c);
            }

            res+=dinic();
            if(res>=k) break;//所有人都接到了
            day++;
        }
        printf("%d\n",day);
    }

    return 0;
}