最近看到了同机房巨佬的帖子,也想探讨一下马蜂。
#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&∈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