[CTSC1999]家园

zzzyc · 2018-03-13 09:31:01 · 个人记录

这道题让我懂得了一个全新的建图方法。。。当我们跑网络流或者费用流的时候。。。如果不能通过建图一边跑完怎么办。。。答案很简单就是跑多变。。。哈哈哈

这里要用到一个Asia不知道从哪里学来的定义叫拆门。。。就是一个题，我可能有很多的子任务，但是他们不能通过直接建立一个图解决。。。

那么我们就可以这样思考（前提是这道题是网络流），他们有什么联系，我们可以通过这些联系建立一个大图，使每个子任务合起来，最后在动态中不断尽行求取就可以了。。。

这道题就是，分别和每一天的地球和月球连inf的边（貌似这玩意可以叫拆门？），然后如果不是第一天，就把上一天的空间站向这一天的连一条inf表示可能有人留在这里。最后把上一天的运输船的位置向这一天的连一条运输船人数的边。

代码：

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define maxn 10001
#define re register
#define inf k
// emm。。。这个东西无所谓。。。
// 只要 >=k 就可以了。。。
using namespace std;
int num=-1,head[maxn],w[maxn],dep[maxn],s,t,cur[maxn];
int p[maxn],hp[maxn],a[651][651],sum,n,m,k,tot;

struct asd{
    int next;
    int to;
} e[maxn<<2];
queue <int> q;

void add(int x,int y,int z)
{
    e[++num].next=head[x];
    e[num].to=y;
    w[num]=z;
    head[x]=num;
}

bool bfs()
{
    while(!q.empty()) q.pop();
    memset(dep,0,sizeof(dep));
    dep[s]=1; q.push(s);
    while(!q.empty())
    {
        int now=q.front(); q.pop();
        for(int i=head[now];i!=-1;i=e[i].next)
            if(w[i]>0 && dep[e[i].to]==0)
            {
                dep[e[i].to]=dep[now]+1;
                q.push(e[i].to);
            }
    }
    if(dep[t]==0) return 0;
    else return 1;
}

int dfs(int u,int dis)
{
    if(u==t) return dis;
    int diss=0;
    for(int i=head[u];i!=-1;i=e[i].next)
        if(w[i]!=0 && dep[e[i].to]==dep[u]+1)
        {
            int disss=dfs(e[i].to,min(dis,w[i]));
            if(disss)
            {
                diss+=disss;
                dis-=disss;
                w[i]-=disss;
                w[i^1]+=disss;
                if(!dis) break;
            }
        }
    return diss;
}

int Dinic()
{
    int ans=0;
    while(bfs())
    {
        for(int i=0;i<=t;i++)
            cur[i]=head[i];
        while(int d=dfs(s,inf))
            ans+=d;
    }
    return ans;
}

int main()
{
    memset(head,-1,sizeof(head));
    cin>>n>>m>>k;
    n+=2;
    s=0; t=1001;
    for(re int i=1;i<=m;i++)
    {
        scanf("%d%d",&p[i],&hp[i]);
        for(re int j=0,x;j<hp[i];j++)
        {
            scanf("%d",&x);
            a[i][j]=x;
            a[i][j]+=2;
        }
    }
    int ans=0;

    while(ans<30)
    {
        add(ans*n+1,t,inf);
        add(t,ans*n+1,0);
        add(s,ans*n+2,inf);
        add(ans*n+2,s,0);
        if(ans!=0)
        {
            for(re int i=1;i<=n;i++)
            {
                add((ans-1)*n+i,ans*n+i,inf);
                add(ans*n+i,(ans-1)*n+i,0);
            }
            for(re int i=1;i<=m;i++)
            {
                int x=a[i][(ans-1)%hp[i]];
                int y=a[i][ans%hp[i]];
                add((ans-1)*n+x,ans*n+y,p[i]);
                add(ans*n+y,(ans-1)*n+x,0);
            }
        }
        sum+=Dinic();
        if(sum>=k) break;
        ans++;
    }
    cout<<((ans<30) ? ans:0);
}