社区讨论

MLE是什么情况

P1231教辅的组成参与者 5已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mi6nx15m
此快照首次捕获于
2025/11/20 07:57
4 个月前
此快照最后确认于
2025/11/20 07:57
4 个月前
查看原帖
dinic开1e6数组,为啥MLE,求大神告知!!
CPP
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int MAXN=1e6+10;
const int INF=1<<29;
inline int read(){
	int out=0;
	char c=getchar();
	while(c<48||c>57) c=getchar();
	while(c<=57&&c>=48){
		out=(out<<3)+(out<<1)+c-48;
		c=getchar();
	}
	return out;
}
inline void write(int x){
	if(x>9) write(x/10);
	putchar(x%10+48);
}
struct Node{int u,v,cap,flow;};
struct dinic{
	vector<Node>edge;
	vector<int>node[MAXN];
	int cur[MAXN],dis[MAXN];
	int n,m=0,s,t;
	void addedge(int u,int v,int cap){
		edge.push_back(Node{u,v,cap,0});
		edge.push_back(Node{v,u,0,0});
		node[u].push_back(m++);
		node[v].push_back(m++);
	}
	bool bfs(){
		bool vis[MAXN];
		memset(vis,0,sizeof(vis));
		queue<int>q;
		vis[s]=1;
		dis[s]=0;
		q.push(s);
		while(!q.empty()){
			int u=q.front();
			q.pop();
			for(int i=0;i<node[u].size();++i){
				Node& e=edge[node[u][i]];
				if(!vis[e.v]&&e.cap-e.flow>0){
					dis[e.v]=dis[u]+1;
					vis[e.v]=1;
					q.push(e.v);
				}
			}
		}
		return vis[t];
	}
	int dfs(int u,int a){
		int flow=0,f;
		if(u==t||!a) return a;
		for(int& i=cur[u];i<node[u].size();++i){
			Node& e=edge[node[u][i]];
			if(dis[e.v]=dis[u]+1&&(f=dfs(e.v,min(a,e.cap-e.flow)))>0){
				e.flow+=f;
				edge[node[u][i]^1].flow-=f;
				a-=f;
				flow+=f;
				if(!a) break;
			}
		}
		return flow;
	}
	int maxflow(int s,int t){
		int flow=0;
		this->s=s,this->t=t;
		while(bfs()){
			memset(cur,0,sizeof(cur));
			flow+=dfs(s,INF);
		}
		return flow;
	}
}G;
void init(){
	int n1=read();
	int n2=read();
	int n3=read();
	G.s=n1*2+n2+n3+1;
	G.t=G.s+1;
	for(int i=1;i<=n2;++i) G.addedge(G.s,i,1);				
	for(int i=G.s-n3;i<G.s;++i) G.addedge(i,G.t,1);
	for(int i=1;i<=n1;++i) G.addedge(n2+i,n2+n1+i,1);
	int m=read();
	for(int i=1;i<=m;++i){
		int u=read();
		int v=read();
		G.addedge(v,u+n2,1);
	}
	m=read();
	int temp=n2+n1;
	int temp1=n2+2*n1;
	for(int i=1;i<=m;++i){
		int u=read();
		int v=read();
		G.addedge(temp+u,v+temp1,1);
	}
}
int main(){
	init();
	write(G.maxflow(G.s,G.t));
	return 0;
}
	

回复

4 条回复,欢迎继续交流。

正在加载回复...