[CTSC1999]家园 分层图网络流_并查集

Code:

#include<cstdio>

#include<vector>

#include<algorithm>

#include<queue>

#include<cstring>

using namespace std;

const int maxn=100;

const int INF=1000000;

# define  pb push_back

int p[maxn],B[50],A[maxn][50];

int s,t;

int find(int x){

	if(p[x]==x)return x;

	return p[x]=find(p[x]);

}

struct loop{

	int to,cap,mod,start;

	loop(int to,int cap,int mod,int start):to(to),cap(cap),mod(mod),start(start){}

};

vector<loop>V[maxn];

struct Edge{

	int from,to,cap;

	Edge(int u,int v,int c):from(u),to(v),cap(c) {}

};

struct Dicnic{

   vector<Edge>edges;

   vector<int>G[maxn];

   int d[maxn],vis[maxn],cur[maxn];

   queue<int>Q;

   int ans=0;

   void addedge(int u,int v,int c){

	edges.pb(Edge(u,v,c));               //正向弧

	edges.pb(Edge(v,u,0));               //反向弧

	int m=edges.size();

	G[u].pb(m-2);

	G[v].pb(m-1);

   }

   int BFS()

   {

	memset(vis,0,sizeof(vis));

	d[s]=0,vis[s]=1;Q.push(s);

	while(!Q.empty()){

		int u=Q.front();Q.pop();

		int sz=G[u].size();

		for(int i=0;i<sz;++i){

			Edge e=edges[G[u][i]];

			if(!vis[e.to]&&e.cap>0){

				d[e.to]=d[u]+1,vis[e.to]=1;

				Q.push(e.to);

			}

		}

	}

	return vis[t];

   }

   int dfs(int x,int a){

	   if(x==t)return a;

	   int sz=G[x].size();

	   int f,flow=0;

	   for(int i=cur[x];i<sz;++i){

		Edge e=edges[G[x][i]];

		cur[x]=i;

		if(d[e.to]==d[x]+1&&e.cap>0){

			f=dfs(e.to,min(a,e.cap));

			if(f)

			{

				int u=G[x][i];

				a-=f;

				edges[u].cap-=f;

				edges[u^1].cap+=f;

				flow+=f;

				if(a==0)break;

			}

		}

	   }

	   return flow;

   }

   int maxflow(){

	while(BFS()){

	  memset(cur,0,sizeof(cur));

	  ans+=dfs(s,INF);

	}

	return ans;

   }

}op;

int main()

{

	int N,M,K;

	scanf("%d%d%d",&N,&M,&K);

	for(int i=0;i<=N+1;++i)A[0][i]=i;

	for(int i=1;i<=100;++i)

		for(int j=0;j<=N+1;++j)A[i][j]=A[i-1][j]+N+2;

	for(int i=0;i<100;++i)p[i]=i;                                                        //init();

	for(int i=1;i<=M;++i)

	{

		int a,b,pre;

		scanf("%d%d",&a,&b);

		for(int j=0;j<b;++j){int mm;scanf("%d",&mm);if(mm==-1)mm=N+1;B[j]=mm;}

		for(int j=0;j<b;++j){

			int u=B[j];

			if(j>0){int x=find(u);int y=find(pre);if(x!=y)p[x]=y;}

			pre=u;

			int nex=(j+1)%b;

			V[u].push_back(loop(B[nex],a,b,j));

		}

	}

	int aa=find(0);

	int bb=find(N+1);

	if(aa!=bb){printf("0");return 0;}

	s=4001,t=4002;

	op.addedge(s,0,K);

	int ans;

	for(ans=0;;++ans){

		for(int u=0;u<=N+1;++u){

			int sz=V[u].size();

			for(int i=0;i<sz;++i){

				loop lp=V[u][i];

				if(ans>=lp.start&&((ans-lp.start)%lp.mod==0))

					op.addedge(A[ans][u],A[ans+1][lp.to],lp.cap);

			}

			if(ans>0)op.addedge(A[ans-1][u],A[ans][u],INF);

		}

		op.addedge(A[ans][N+1],t,INF);

		int yy=op.maxflow();

		if(yy==K)break;

	}

	printf("%d",ans);

	return 0;

}