代码求调,全MLE和TLE
查看原帖
代码求调,全MLE和TLE
560291
the_Dream_Chaser楼主2023/12/1 20:26
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=4e4+10;
const int M=1e6+10;

int n1,n2,n3,m1,m2;
int w,dis[MAXN];
int head[MAXN],pre[MAXN],cnr[MAXN],tot=1;
int id(int p,int x) {  //编号 
	switch(p) {
		case 1: return x;
		case 2: return n2+x;
		case 3: return n2+n1+x;
		case 4: return n2+n1+n1+x;
	}
}
struct Edge{
	int to,next;
	int val;
}e[M];
void add(int u,int v,int w){
	e[++tot].to=v;
	e[tot].val=w;
	e[tot].next=head[u];
	head[u]=tot;
	e[++tot].to=u;
	e[tot].val=0;
	e[tot].next=head[v];
	head[v]=tot;
}

int bfs(int s,int t){
	memset(dis,0,sizeof(dis));
	memcpy(cnr,head,sizeof(head));
	queue<int> q;
	q.push(s);
	dis[s]=1;
	cout<<s<<" ";
	while(!q.empty()){
		int u=q.front();
//		cout<<u<<endl;
		q.pop();
		for(int i=head[u];i;i=e[i].next){
			int v=e[i].to;
			if(!dis[v] && e[i].val)
				dis[v]=dis[u]+1;
				q.push(v);
		}
	}
	return dis[t];
}
int dfs(int u,int v,int w){
	if(u==v)return w;
	int ans=0;
	for(int i=cnr[u];i&&ans<w;i=e[i].next){
		cnr[u]=i;
		int x=e[i].to;
		if(e[i].val&&dis[x]==dis[u]+1){
			int o=dfs(x,v,min(e[i].val,(w-ans)));
			if(o){
				e[i].val-=o;
				e[i^1].val+=o;
				ans+=o;
			}
		}
		
	}
	if(ans<w)dis[u]=-1;
	return ans;
}
/*void update(){
	int x=t;
	while(x!=s){
		int k=pre[x];
		e[k].val-=dis[t];
		e[k^1].val+=dis[t];
        x=e[k^1].to;
	}
	ans+=dis[t];
}*/
int dinic(int s,int t){
	int ans=0;
	while(bfs(s,t)){
//		cout<<1111<<endl;
		int x;
		while((x=dfs(s,t,1<<29)))ans+=x; 
	}
	return ans;
}
int main(){
	cin>>n1>>n2>>n3;
	cin>>m1>>m2;
	for(int i=m1;i>0;i--){
		int u,v;
		cin>>u>>v;
		add(id(1,v),id(2,u),1);
	}
	for(int i=m2;i>0;i--){
		int u,v;
		cin>>u>>v;
		add(id(3,u),id(4,v),1);
	}
	int T=n1+n2+n1+n3+1;
	for(int i=1;i<=n1;++i)add(id(2,i),id(3,i),1);
	for(int i=1;i<=n2;++i)add(0,id(1,i),1);
	for(int i=1;i<=n3;++i)add(id(4,i),T,1);
	
	cout<<dinic(0,T)<<endl;
	return 0;
}

/*
5 3 4
5
4 3
2 2
5 2
5 1
5 3
5
1 3
3 1
2 2
3 3
4 3


ans=2
*/
2023/12/1 20:26
加载中...