萌新 TLE 30pts 求助
查看原帖
萌新 TLE 30pts 求助
238861
xzzduang楼主2021/7/20 11:37
#include<iostream>
#include<stdio.h>
#include<string.h>
#define N 105
#define INF 0x3f3f3f3f
#define R register
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*f;
}
struct edge{
	int b,c,n;
}d[6*N*N+4*N];
int n,F,D,h[4*N],tot=1,s,t,cur[N],q[4*N],head,tail,dep[4*N];
void charu(int a,int b,int c){
	d[++tot].b=b,d[tot].c=c,d[tot].n=h[a],h[a]=tot;
}
bool bfs(){
	head=1,tail=0;
	memset(dep,0,sizeof(dep));
	dep[q[++tail]=s]=1;
	while(head<=tail){
		int u=q[head++];
		for(R int i=h[u];i;i=d[i].n){
			if(d[i].c && !dep[d[i].b]) dep[q[++tail]=d[i].b]=dep[u]+1;
		}
	}
	return dep[t];
}
int dfs(int u,int flow){
	if(u==t) return flow;
	for(R int &i=cur[u];i;i=d[i].n){
		if(d[i].c && dep[d[i].b]==dep[u]+1){
			int tmp=dfs(d[i].b,min(d[i].c,flow));
			if(!tmp) continue;
			d[i].c-=tmp,d[i^1].c+=tmp;
			return tmp;
		}
	}
	return 0;
}
int dinic(){
	int res=0,tmp;
	while(bfs()){
		memcpy(cur,h,sizeof(cur));
		while(tmp=dfs(s,INF)!=0) res+=tmp;
	}
	return res;
}
int main(){
	n=read(),F=read(),D=read();
	for(R int i=1;i<=n;++i){
		int a=read(),b=read();
		for(R int j=1;j<=a;++j){
			int x=read();
			charu(x,i+F,1);
			charu(i+F,x,0);
		}
		for(R int j=1;j<=b;++j){
			int x=read();
			charu(F+n+i,F+2*n+x,1);
			charu(F+2*n+x,F+n+i,0);
		}
	}
	for(R int i=1;i<=F;++i) charu(0,i,1),charu(i,0,0);
	for(R int i=1;i<=n;++i) charu(F+i,F+n+i,1),charu(F+n+i,F+i,0);
	t=F+2*n+D+1;
	for(R int i=1;i<=D;++i) charu(F+2*n+i,t,1),charu(t,F+2*n+i,0);
	printf("%d",dinic());
	return 0;
}

2021/7/20 11:37
加载中...