WA on #2 #6 #9 #10

P2754 [CTSC1999]家园 / 星际转移问题

#include<bits/stdc++.h>
using namespace std;
int n,m,k,r[25][25],h[25],ans;
#define pos(i,j) ((i)+((n+3)*(j)))
#define moon (n+1)
#define inf 0x3f3f3f3f
int s=5001,t=5002;
struct MF{
	struct edge{int nt,v,w;}e[5005*5005];
	#define vt e[i].v
	#define ntt e[i].nt
	#define wt e[i].w
	int head[505*50],cur[505*50],tot=1;
	int dis[505*50];
	int maxflow=0;
	void addedge(int u,int v,int w){
		e[++tot]={head[u],v,w};
		head[u]=tot;
		e[++tot]={head[v],u,0};
		head[v]=tot;
	}
	bool bfs(){
		memset(dis,0,sizeof(dis));
		memcpy(cur,head,sizeof(head));
		queue<int>q;
		q.push(s);
		dis[s]=1;
		while(q.size()){
			int u=q.front();
			q.pop();
			for(int i=head[u];i;i=ntt){
				if(wt&&!dis[vt]){
					dis[vt]=dis[u]+1;
					q.push(vt); 
				}
			}
		}
		return dis[t];
	}
	int dfs(int u,int mflow){
		if(u==t)return mflow;
		int ret=0;
		for(int &i=cur[u];i;i=ntt){
			if(wt&&dis[vt]==dis[u]+1){
				int op=dfs(vt,min(mflow,wt));
				if(op)mflow-=op,wt-=op,e[i^1].w+=op,ret+=op;
				if(mflow==0)return ret;
			}
		}
		return ret;
	}
	void dinic(){
		while(bfs()){
			int x=0;
			while((x=dfs(s,inf)))maxflow+=x;
		}
	}
}mp;
struct link{
	int f[1005];
	void init(){
		for(int i=0;i<=1005;i++)f[i]=i;
	}
	int find(int x){return f[x]==x?x:(f[x]=find(f[x]));}
	void mer(int x,int y){
		x=find(x),y=find(y);
		if(x==y)return;
		f[x]=y;
	}
	void check(){
		if(find(0)==find(moon))return;
		cout<<0;
		exit(0);
	}
}ct;
int main(){
	scanf("%d%d%d",&n,&m,&k);
	ct.init();
	for(int i=1;i<=m;i++){
		scanf("%d%d",h+i,r[i]);
		for(int j=1;j<=r[i][0];j++){
			scanf("%d",r[i]+j);
			if(r[i][j]==-1)r[i][j]=moon;
			if(j>1)ct.mer(r[i][j],r[i][j-1]);
		}
	}
	ct.check();
	for(ans=0;;ans++){
		mp.addedge(pos(moon,ans),t,inf);
		if(ans!=0){
			for(int i=0;i<=n;i++){
				mp.addedge(pos(i,ans-1),pos(i,ans),inf);
			}
			for(int i=1;i<=m;i++){
				int u=r[i][(ans+r[i][0]*2-2)%r[i][0]+1],v=r[i][(ans+r[i][0]-1)%r[i][0]+1];
				u=pos(u,ans-1);
				v=pos(v,ans);
				mp.addedge(u,v,h[i]);
			}
		}else{
			mp.addedge(s,pos(0,0),inf);
		}
//		cout<<pos(moon,ans)<<endl;
		mp.dinic();
//		cout<<mp.maxflow<<' '<<ans<<endl;
		if(mp.maxflow>=k){
			cout<<ans-1;
			break;
		}
	}
	return 0;
}