超级大水题

Description

 史努比最爱水题了，他知道现在他要挑战的是一道超级大水题哦。不过因为太水了，而且他又很懒,所以把这道水题推给了你们。

有n个(不包括ZSTU和火车东站)车站介于ZSTU和火车东站之间，一共有m辆公交车往返于这些车站和火车东站。每个车站假设可以站无数个人，每辆车最多承载H[i]个人，经过S[i]个车站。假设一辆车依次经过1,2,3，这三个车站，那么它将一直往复1->2->3->1->2...现在认为车从一个站到下一个站要花费1个小时，人只能在车站或ZSTU,火车东站上下车，初始时有k个人在ZSTU（0站）,所有的车都在初始站（所给车站的第一个车站为初始站)，现在问你们最快让全部人从ZSTU到火车东站要多少小时。所有车同时运行。

Input

 第一行有一个T<=10，表示T组测试样例，第二行三个数n(车站数目),m(车数目),k(人数)，(n<=13,m<=20,k<=50);接下来的m行给出车信息,每行给出H[i](能承载的最大人数),S[i](经过的车站数目),还有依次给出S[i]个车站编号。ZSTU用0编号表示，火车东站用-1表示。

Output

 若无解则输出-1，否则逐行输出答案。

Sample Input

2 2 2 1 1 3 0 1 2 1 3 1 2 -1 2 3 3 1 2 0 2 1 2 1 2 1 2 1 -1

Sample Output

5 7

HINT

 第一个样例，一人从0站乘坐1号公交车途径1站，到2站下车，花费2S；此时2号车位于-1站，再经过2S，2号车从-1站途径1站到2站，人上2号车再经过1S到达-1站，共花费5S。或者一人从0站乘坐一号公交车到1站下车，花费1S，此时2号车位于2站，再经过2S到1站，人上2号车再经过2S到达-1站，共花费5S。

题解：

首先判断学校到火车东站能不能到站，即是否在同一个集团里面，用并查集就可以了。然后跑网络流，网络流跑一次后会更改原来储存的边的信息，因此可以枚举时间进行网络流，按照时间建边，在上一个时间段跑网络流的基础上，继续建图在继续跑网络流，将每次的最大流加起来直到总和大于等于k就可以返回当前天数了。

具体操作是将第i-1小时的第j个车的信息向第i小时的第j个车进行连边，容量为INF，将每辆车第i-1小时所待的公交车站向第i小时所待的公交车站连边，容量为车的最大载人数。

#include <bits/stdc++.h>
//CLOCKS_PER_SEC
#define se second
#define fi first
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define Pii pair<int,int>
#define Pli pair<ll,int>
#define ull unsigned long long
#define pb push_back
#define fio ios::sync_with_stdio(false);cin.tie(0)
const double Pi=3.14159265;
const int N=1e3+5;
const ull base=163;
const int INF=0x3f3f3f3f;
using namespace std;
int n,m,k,s,t;
int head[10100],to[100010],cur[10100],nx[100010];
int cap[100010];
int tot=0;
void add(int x,int y,int c){
    to[tot]=y;
    nx[tot]=head[x];
    cap[tot]=c;
    head[x]=tot++;
    
    to[tot]=x;
    nx[tot]=head[y];
    cap[tot]=0;
    head[y]=tot++;
}
void init(int n){
    tot=0;
    memset(head,-1,sizeof(head));
}
int d[N];
int bfs(){
    memset(d,-1,sizeof(d));
    queue<int>q;
    q.push(s);
    d[s]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=head[u];~i;i=nx[i]){
            int v=to[i];
            if(d[v]==-1&&cap[i]>0){
                d[v]=d[u]+1;
                q.push(v);
            }
        }
    }
    return d[t]!=-1;
}
int dfs(int s,int a){
    if(s==t||a==0)return a;
    int flow=0,f;
    for(int &i=cur[s];~i;i=nx[i]){
        int v=to[i];
        if(d[s]+1==d[v] && cap[i]>0 && (f=dfs(v,min(a,cap[i])))>0){
            flow+=f;
            cap[i]-=f;
            cap[i^1]+=f;
            a-=f;
            if(a==0)break;
        }
    }
    return flow;
}
int dinic(){
    int ans=0;
    while(bfs()){
        for(int i=0;i<=1000;i++)cur[i]=head[i];
        while(int di=dfs(s,INF)){
            ans+=di;
        }
    }
    return ans;
}
int ship[N][N];
int num[N];
int r[N];
int fa[N];
int F(int x){
    return fa[x]==x?x:fa[x]=F(fa[x]);
}

bool check(int x,int y){
    if(F(x)==F(y))return 1;
    else return 0;
}
int cal(int a,int d){
    return d*n+a;
}
void solve(){
    int flow=0;
    int i;
    init(n);// n -1     n-1   0
    add(s,cal(n-1,0),INF);
    add(cal(n,0),t,INF);
    for(i=1;flow<k;i++){
        add(s,cal(n-1,i),INF);add(cal(n,i),t,INF);
        for(int j=1;j<=n;j++){
            add(cal(j,i-1),cal(j,i),INF);
        }
        for(int j=1;j<=m;j++){
            int a=(i-1)%num[j]+1;
            int b=i%num[j]+1;
            add(cal(ship[j][a],i-1),cal(ship[j][b],i),r[j]);
        }
        flow+=dinic();
        
    }
   printf("%d\n",i-1);
}
int main(){
	 // clock_t start, end;
    int T;scanf("%d",&T);
    while(T--){
        s=0,t=1000;
        scanf("%d%d%d",&n,&m,&k);
        for(int i=0;i<=n+2;i++)fa[i]=i;
        for(int i=1;i<=m;i++){
            scanf("%d%d",&r[i],&num[i]);
            for(int j=1;j<=num[i];j++){
                scanf("%d",&ship[i][j]);
                if(ship[i][j]==0)ship[i][j]=n+1;
                if(ship[i][j]==-1)ship[i][j]=n+2;
                if(j>1){
                    fa[F(ship[i][j-1])]=F(ship[i][j]);
                }
            }
        }
        n+=2;
        if(check(n, n-1)){
            solve();
        }
        else{
            printf("0\n");
        }
    }
    // end = clock();
    // cout << "time :"<<(double)(end - start) / CLOCKS_PER_SEC << endl;
    return 0;
}
/*

*/