P2754 [CTSC1999]家园

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=10000+10;
const int M=100000+100;
const int INF=0x3f3f3f3f;
int n,m,k,s,t,p[30];
vector<int> V[30];
struct edge{
    int nxt,to,cap;
}edges[M<<1];
int cnt=1,head[N],cur[N];

void add_edge(int x,int y,int z) {
    edges[++cnt].nxt=head[x]; edges[cnt].to=y; edges[cnt].cap=z; head[x]=cnt;
}

int dep[N]; 
queue<int> q;
bool bfs() {
    while (!q.empty()) q.pop();
    memset(dep,0,sizeof(dep));
    dep[s]=1; q.push(s);
    while (!q.empty()) {
        int x=q.front(); q.pop();
        for (int i=head[x];i;i=edges[i].nxt) {
            edge e=edges[i];
            if (!dep[e.to] && e.cap) {
                dep[e.to]=dep[x]+1;
                q.push(e.to);
            }
        }
    }
    return dep[t];
}

int dfs(int x,int lim) {
    if (x==t) return lim;
    for (int& i=cur[x];i;i=edges[i].nxt) {
        edge e=edges[i];
        if (dep[x]+1==dep[e.to] && e.cap) {
            int flow=dfs(e.to,min(lim,e.cap));
            if (flow>0) {
                edges[i].cap-=flow;
                edges[i^1].cap=+flow;
                return flow;  //找到一条增广路就要return 
            }
        }
    }
    return 0;
}

int Dinic() {
    int maxflow=0;
    while (bfs()) {
        for (int i=s;i<=t;i++) cur[i]=head[i];  //当前弧优化 
        while (int flow=dfs(s,INF)) maxflow+=flow;
    }
    return maxflow;
}

void build(int day) {
    cnt=1; memset(head,0,sizeof(head));
    s=0; t=n*day+1;
    for (int i=1;i<=m;i++) {
        int lst=0;
        for (int j=1;j<day;j++) {
            int now=lst+1;
            if (now>=V[i].size()) now=0;
            int u=V[i][lst],v=V[i][now];
            if (u==0) u=s; else if (u==-1) u=t; else u=(j-1)*n+u;
            if (v==0) v=s; else if (v==-1) v=t; else v=(j)*n+v;
            if (u!=t && v!=s) add_edge(u,v,p[i]),add_edge(v,u,0);
            lst=now;
        }
    }
    for (int j=0;j<day-1;j++)
        for (int i=1;i<=n;i++) {
            add_edge(j*n+i,(j+1)*n+i,INF);
            add_edge((j+1)*n+i,j*n+i,0);
        }
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1;i<=m;i++) {
        int t; scanf("%d%d",&p[i],&t);
        for (int j=1;j<=t;j++) {
            int x; scanf("%d",&x);
            V[i].push_back(x);
        }
    }
    
    for (int i=1;i;i++) {
        build(i);
        int tmp=Dinic();
        if (tmp>=k) { printf("%d\n",i-1); break; }
        if (i>=1000) { printf("%d",0); break; }
    }
    return 0;
}