萌新刚学网络流,求大佬看看第七个点为什么超时
查看原帖
萌新刚学网络流,求大佬看看第七个点为什么超时
53769
北文楼主2023/5/26 09:26
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5, inf=1e15;
int S, T;
struct Edge{
	int v, w, nxt;
}e[N<<1];
int cnt=1, h[N], cur[N], dis[N];
void add(int u, int v, int w) {
	e[++cnt]=Edge{v, w, h[u]};
	h[u]=cnt;
	e[++cnt]=Edge{u, 0, h[v]};
	h[v]=cnt;
}
bool bfs() {
	for(int i=0; i<=T; i++)
		cur[i]=h[i], dis[i]=0;
	queue<int>q;
	q.push(S); dis[S]=1;
	while(!q.empty()) {
		int u=q.front();
		q.pop();
		for(int i=h[u]; i; i=e[i].nxt) {
			if(e[i].w) {
				int v=e[i].v;
				if(!dis[v]) {
					dis[v]=dis[u]+1;
					if(v==T) {
						while(!q.empty()) q.pop();
						return 1;
					}
					q.push(v);
				}
			}
		}
	}
	return 0;
}
int dfs(int u, int flow) {
	if(!flow||u==T) return flow;
	int get=0;
	for(int &i=cur[u]; i; i=e[i].nxt) {
		int v=e[i].v;
		if(dis[v]==dis[u]+1) {
			if(e[i].w) {
				int sav=dfs(v, min(flow, e[i].w));
				if(sav) {
					e[i].w-=sav;
					e[i^1].w+=sav;
					flow-=sav;
					
					get+=sav;
				}
				else dis[v]=-1;
			}
		}
	}
	return get;
}
int p, n, c, vis[N];
int main() {
	scanf("%d %d %d", &p, &c, &n);
	S=0; T=p*2+1;
	for(int i=1; i<=c; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		add(u, v+p, inf);
		add(v, u+p, inf);
	}
	add(1+p, T, inf);
	
	for(int i=1; i<=n; i++) {
		int u;
		scanf("%d", &u);
		add(S, u, inf);
		vis[u]=1;
	}
	for(int i=1; i<=p; i++) 
	if(!vis[i]) add(i+p, i, 1);
	else add(i+p, i, inf);
	int ans=0;
	while(bfs()) ans+=dfs(S, inf);
	printf("%d", ans);
	return 0;
}
2023/5/26 09:26
加载中...