萌新刚学OI,求助板子问题。
查看原帖
萌新刚学OI,求助板子问题。
602803
_qingshu_楼主2023/12/19 19:46

第一版写的 hlpp 80pts,改了一个下午没有改过。然后我试着把板子改成了 Dinic 就过了??有大佬可以帮忙看看吗?

hlpp 代码我放下面了。

#include<bits/stdc++.h>
using namespace std;
int n,m,s,t,ouye;
struct edge{
	int to,nxt;
	int val;
}e[10200010];
int head[10200010],tot=1; 
int over[10200010],vist[10200010];
int gap[10200010],h[10200010];
struct cmp{
	bool operator()(int x,int y)const{
		return h[x]<h[y];
	}
};
priority_queue<int,vector<int>,cmp>qq;
void add(int u,int v,int w){
	e[++tot].to=v;
	e[tot].nxt=head[u];
	head[u]=tot;
	e[tot].val=w;
	
	e[++tot].to=u;
	e[tot].nxt=head[v];
	head[v]=tot;
	e[tot].val=0;
}
bool bfs(){
	memset(h,0x3f,sizeof h);
	h[t]=0;
	queue<int>q;
	q.push(t);
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=e[i].nxt){
			int v=e[i].to;
			if(h[v]>h[x]+1&&e[i^1].val){
				h[v]=h[x]+1;
				q.push(v);
			}
		}
	}
	return (h[s]!=0x3f3f3f3f);
}
void push(int x){
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].to;
		if(e[i].val&&h[x]==h[v]+1){
			int k=min(e[i].val,over[x]);
			e[i].val-=k;
			e[i^1].val+=k;
			over[x]-=k;
			over[v]+=k;
			if(v!=s&&v!=t&&!vist[v]){
				qq.push(v);
				vist[v]=1;
			}
			if(!over[x]){
				return;
			}
		}
	}
}
void relable(int x){
	h[x]=0x3f3f3f3f;
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].to;
		if(e[i].val&&h[x]>h[v]+1){
			h[x]=h[v]+1;
		}
	}
}
long long hlpp(){
	if(!bfs()){
		return 0;
	}
	h[s]=2*n+1;
	for(int i=1;i<=2*n+1;i++){
		if(h[i]!=0x3f3f3f3f){
			gap[h[i]]++;
		}
	}
	for(int i=head[s];i;i=e[i].nxt){
		int v=e[i].to;
		if(e[i].val){
			over[v]+=e[i].val;
			e[i^1].val=e[i].val;
			e[i].val=0;
			if(v!=s&&v!=t&&!vist[v]){
				qq.push(v);
				vist[v]=1;
			}
		}
	}
	while(!qq.empty()){
		int x=qq.top();
		qq.pop();
		vist[x]=0;
		push(x);
		if(over[x]){
			gap[h[x]]--;
			if(!gap[h[x]]){
				for(int i=1;i<=2*n+1;i++){
					if(i!=s&&i!=t&&h[i]>h[x]&&h[i]<=2*n+1){
						h[i]=2*n+2;
					}
				}
			}
			relable(x);
			gap[h[x]]++;
			vist[x]=1;
			qq.push(x);
		}
	}
	return over[t];
}
long long no[5200010];
int main(){
	cin>>n>>m>>ouye;
	t=1;
	s=2*n+1;
	for(int i=1,u,v;i<=m;i++){
		cin>>u>>v;
		add(u+n,v,0x3f3f3f3f);
		add(v+n,u,0x3f3f3f3f);
	}	
	for(int i=1,u;i<=ouye;i++){
		cin>>u;
		no[u]=1;
		add(s,u,0x3f3f3f3f);
	}
	for(int i=1;i<=n;i++){
		if(no[i]){
			add(i,i+n,0x3f3f3f3f);
		}
		else{
			add(i,i+n,1);
		}
	}
	cout<<hlpp();
}

2023/12/19 19:46
加载中...