题解 P2754 【星际转移问题】

· · 题解

/* 1.从源点向每一天的地球链接一条INF

2.从每一天的月亮向汇点链接一条INF

3.从上一天的每一个节点向当天的对应节点链接一条INF（因为人们可以留在中转站等一等嘛）

4.针对每一艘飞船，获取其上一天的位置，再获取这一天的位置，在这两个点之间连一条容量为飞船满载人数的流

每次新加一天然后跑到最大流超过k即可

至于无解的情况只要当ans达到一个很大的值的时候跳出来即可

参考题解，本来以为是费用流+周期判断~~~

*/

#include<cstdio>
#include<cstring>
#define min(x,y) ((x)<(y)?(x):(y))
#define inf 2147483647
    struct node{int x,y,c,next,other;} a[100000];
    int last[100000],peo[201],le[201];
    int map[201][201];
    int n,m,k,len=0,ans=0,sum=0,st=0,ed=9999;
void ins(int x,int y,int c)
{
    a[++len].x=x;a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;a[len].other=len+1;
    a[++len].x=y;a[len].y=x;a[len].c=0;a[len].next=last[y];last[y]=len;a[len].other=len-1;
}
int f[100000],h[100000];
bool bfs()
{
    int head=1,tail=2;
    memset(h,0,sizeof(h));
    h[st]=1;
    f[1]=st;
    while(head<tail)
    {
        int x=f[head];
        for(int i=last[x];i!=-1;i=a[i].next)
        {
            int y=a[i].y;
            if(a[i].c>0&&h[y]==0)
            {
                h[y]=h[x]+1;
                f[tail++]=y;
            }
        }
        head++;
    }
    if(h[ed]>0) return true; else return false;
}
int dfs(int x,int f)
{
    int s=0,t;
    if(x==ed) return f;
    for(int i=last[x];i!=-1;i=a[i].next)
    {
        int y=a[i].y;
        if(a[i].c>0&&h[y]==h[x]+1&&f>s)
        {
            s+=(t=(dfs(y,min(f-s,a[i].c))));
            a[i].c-=t;
            a[a[i].other].c+=t;
        }
    }
    if(s==0) h[x]=0;
    return s;
}
int dinic()
{
    int flow=0;
    while(bfs())
        flow+=dfs(st,inf);
    return flow;
}
int main()
{
    memset(last,-1,sizeof(last));
    scanf("%d %d %d",&n,&m,&k);
    n+=2;
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&peo[i],&le[i]);
        for(int j=0;j<le[i];j++)
        {
            scanf("%d",&map[i][j]);
            map[i][j]+=2;
        }
    }
    while(ans<500)
    {
        ins(ans*n+1,ed,inf);
        ins(st,ans*n+2,inf);    
        if(ans!=0)
        {
            for(int i=1;i<=n;i++)
                ins((ans-1)*n+i,ans*n+i,inf);
            for(int i=1;i<=m;i++)
            {
                int x=map[i][(ans-1)%le[i]];
                int y=map[i][ans%le[i]];
                ins((ans-1)*n+x,ans*n+y,peo[i]);
            }
        }
        sum+=dinic();
        if(sum>=k) break;
        ans++;
    }
    if(ans==500) printf("0"); else printf("%d",ans);
}