70pts求调
查看原帖
70pts求调
999274
CNS_5t0_0r2楼主2025/1/20 14:41
#include<bits/stdc++.h>
using namespace std;
const int N0 = 209,N = N0 << 2,M = N * N * N;
int n,f,d,s,t;
int ans;
struct edge{
	int to,cap,nex;
} e[M << 1];
int head[N],ecnt = 1;
int head2[N];//分层图的表头 
void addedge(int u,int v,int c){
	ecnt++;
	e[ecnt] = (edge){v,c,head[u]};
	head[u] = ecnt;
}
queue<int> que;
int dep[N];//层次 
bool bfs(){//构造分层图 
	memset(dep,0,sizeof dep);
	que.push(s);
	dep[s] = 1;
	head2[s] = head[s];
	while(!que.empty()){
		int u = que.front();
		que.pop();
		for(int i = head[u];i;i = e[i].nex){
			int v = e[i].to,c = e[i].cap;
			if(dep[v] || !c)
				continue;
			head2[v] = head[v];
			dep[v] = dep[u] + 1;
			que.push(v);
		}
	}
	return dep[t];
}
int dfs(int u,int flow){//在分层图上增广 
	if(u == t)
		return flow;
	int rest = flow,tmp;
	for(int i = head2[u];i && rest;i = e[i].nex){
		head2[u] = i;
		int v = e[i].to,c = e[i].cap;
		if(dep[v] != dep[u] + 1 || !c)
			continue;
		tmp = dfs(v,min(rest,c));
		if(!tmp)
			dep[v] = 0;//当无法从v 增广时,将v从分层图中删除
		e[i].cap -= tmp;
		e[i ^ 1].cap += tmp;
		rest -= tmp;
	}
	return flow - rest;//流到u的流量减去流出u后剩余的流量就是流到汇点的流量
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> f >> d;
	for(int i = 1;i <= n;i++){
		int F,D;
		cin >> F >> D;
		for(int j = 1;j <= F;j++){
			int tmp;
			cin >> tmp;
			addedge(tmp,i + f,1);
			addedge(i + f,tmp,0);
		}
		for(int j = 1;j <= D;j++){
			int tmp;
			cin >> tmp;
			addedge(i + f + n,tmp + f + n + n,1);
			addedge(tmp + f + f + n,i + f + n,0);
		}
	}
	for(int i = 1;i <= n;i++){
		addedge(i + f,i + f + n,1);
		addedge(i + f + n,i + f,0);
	}
	s = 0;t = f + n + n + d + 1;
	for(int i = 1;i <= f;i++){
		addedge(s,i,1);
		addedge(i,s,0);
	}
	for(int i = f + n + n + 1;i <= f + n + n + d;i++){
		addedge(i,t,1);
		addedge(t,i,0);
	}
	int flow = 0;
	while(bfs())
		while(flow = dfs(s,f + 1))
			ans += flow;
	cout << ans;
	return 0;
}
2025/1/20 14:41
加载中...