关于马蜂
  • 板块灌水区
  • 楼主Paracelestia
  • 当前回复13
  • 已保存回复13
  • 发布时间2022/11/7 21:03
  • 上次更新2023/10/27 03:53:17
查看原帖
关于马蜂
542876
Paracelestia楼主2022/11/7 21:03

最近看到了同机房巨佬的帖子,也想探讨一下马蜂。

#include<bits/stdc++.h>
using namespace std;
#define N 114514
#define M 1919810
#define inf 0x3f3f3f3f
struct edg {
	int to,val,nxt;
}e[M];
int head[N],tot=1;
void add(int u,int v,int w) {
	e[++tot]={v,w,head[u]};
	head[u]=tot;
	e[++tot]={u,0,head[v]};
	head[v]=tot;
}
int n,m,s,t;
int c;
int dep[N];
bool des[N];
inline bool bfs() {
	memset(dep,0,sizeof dep);
	dep[s]=1;
	queue<int>q;
	q.emplace(s);
	while(!q.empty()) {
		int u=q.front();q.pop();
		for(int i=head[u];i;i=e[i].nxt) {
			int v=e[i].to,w=e[i].val;
			if(w&&dep[v]==0) dep[v]=dep[u]+1,q.emplace(v);
		}
	}
	return dep[t];
}
inline int dfs(int u,int in) {
	if(u==t) return in;
	int out=0;
	for(int i=head[u];i&&in;i=e[i].nxt) {
		int v=e[i].to,w=e[i].val;
		if(w&&dep[v]==dep[u]+1) {
			int k=dfs(v,min(in,w));
			e[i].val-=k,in-=k;
			e[i^1].val+=k,out+=k;
		}
	}
	if(!out) dep[u]=-1;
	return out;
}
int dinic() {
	int res=0;
	while(bfs()) res+=dfs(s,inf);
	return res;
}
int main() {
	scanf("%d%d%d",&n,&m,&c);
	s=0,t=2*n+1;
	add(s,1,inf);
	add(1,1+n,inf);
	for(int i=1;i<=m;i++) {
		int u,v;
		scanf("%d%d",&u,&v);
		add(u+n,v,inf);
		add(v+n,u,inf);
	}
	for(int i=1;i<=c;i++) {
		int x;
		scanf("%d",&x);
		des[x]=1;
		add(x,x+n,inf);
		add(x+n,t,inf);
	}
	for(int i=2;i<=n;i++) 
		if(!des[i]) add(i,i+n,1);
	printf("%d\n",dinic());
	return 0;
}

(某道网络流题的代码)

我的马蜂我自己感觉还行,但是机房里的人褒贬不一。

而且机房里还有向上面那个帖子里那样的群魔乱舞的奇怪马蜂,所以有个性的马蜂真的很重要吗?QwQ

2022/11/7 21:03
加载中...