[CTSC1999] 家园

佚名 5年前 (2018-12-24) 算法 862人围观抢沙发百度已收录

使用并查集判断无解。
令月球是n+1，地球是0
枚举时长t，将点（地球、月球以及太空站）i拆为t个点(i,j)表示第j时刻的点i。
对于太空船云云建图，容量是h[i]。
源点S和(0,0)连边，容量k。
(n+1,*)和汇点连边，容量k。
跑最大流，判断其是否≥k。

每一次答案可以考虑利用残余网络，虽然有点麻烦就是了。。
代码里没写UFS。。懒得了。。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int N=5e4+5;
const int L=5e6+5;
const int inf=0x3f3f3f3f;

int S=N-1,T=N-2;
int head[N],to[L],upp[L],last[L],cnt=1;
int que[N],lev[N],hd,tl;

inline void add_edge(int x,int y,int u) {
    to[++cnt]=y,upp[cnt]=u,last[cnt]=head[x],head[x]=cnt;
    to[++cnt]=x,upp[cnt]=0,last[cnt]=head[y],head[y]=cnt; 
}
inline bool bfs() {
    memset(lev,0,sizeof lev);
    lev[S]=1;
    que[hd=0,tl=1]=S;
    while(hd<tl) {
        int x=que[++hd];
        for(int i=head[x]; i; i=last[i]) if(upp[i]>0 && !lev[to[i]]) 
            lev[to[i]]=lev[x]+1, que[++tl]=to[i];
    }
    return lev[T]!=0;
}
int dfs(int x,int tf) {
    if(x==T) return tf;
    int tot=0,tmp;
    for(int i=head[x]; i; i=last[i]) if(upp[i]>0 && lev[x]+1==lev[to[i]]) {
        tmp=dfs(to[i],min(tf-tot,upp[i]));
        if(tmp) upp[i]-=tmp,upp[i^1]+=tmp,tot+=tmp;
        if(tot==tf) break;
    }
    if(!tot) lev[x]=-1;
    return tot;
}

int n,m,k;
int h[N];
vector<int> a[N];

inline int I(int x,int t) { return t*(n+2)+x+1;}

int main() {
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1,k,x; i<=m; ++i) {
        scanf("%d%d",h+i,&k);
        while(k--) {
            scanf("%d",&x);
            if(x==-1) x=n+1;
            a[i].push_back(x);
        }
    }
    int ans=0;
    for(int t=0; t<=500; ++t) {
        add_edge(S,I(0,t),inf);
        add_edge(I(n+1,t),T,inf);
        if(t) {
            for(int i=1; i<=m; ++i) {
                int x=a[i][(t-1)%a[i].size()];
                int y=a[i][t%a[i].size()];
                add_edge(I(x,t-1),I(y,t),h[i]);
            }
            for(int i=1; i<=n; ++i) {
                add_edge(I(i,t-1),I(i,t),inf);
            } 
        }
        while(bfs()) ans+=dfs(S,inf);
        if(ans>=k) {
            printf("%d\n",t);
            return 0;
        }
    }
    printf("0"); 
    return 0;
}