这样连边布星qwq
by star_magic_young @ 2018-06-05 11:04:26
@[star_magic_young](/space/show?uid=38372) 哦，是，我改了一下，还是80但wa的点不一样了
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
const int inf=1e9+7;
int s,t,level[110000],cur[110000],cnt;
int head[110000],to[210000],nxt[210000],w[210000];
inline void add(int x,int y,int v){
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
w[cnt]=v;
to[++cnt]=x;
nxt[cnt]=head[y];
head[y]=cnt;
w[cnt]=0;
}
inline bool bfs(){
memset(level,-1,sizeof(level));
queue<int>q;
level[s]=0;
q.push(s);
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(level[y]==-1&&w[i]){
level[y]=level[x]+1;
if(y==t)return 1;
q.push(y);
}
}
}
return 0;
}
inline int dfs(int x,int y,int f){
if(x==y)return f;
int res=0;
if(!cur[x])cur[x]=head[x];
for(int i=cur[x];i;i=nxt[i]){
cur[x]=i;
int j=to[i];
if(level[j]==level[x]+1&&w[i]){
int nf=dfs(j,y,min(f-res,w[i]));
res+=nf;
w[i]-=nf;
w[i^1+2]+=nf;
}
}
if(!res)level[x]=-1;
return res;
}
int main()
{ int n,m,i,j,k,x,y,ans=0;
scanf("%d%d%d%d",&n,&m,&s,&t);
for(i=1;i<=n;i++)
add(i,i+n,1);
for(i=1;i<=m;i++){
scanf("%d%d",&x,&y);
add(x+n,y,inf);
add(y+n,x,inf);
}
s+=n;
while(bfs()){
memset(cur,0,sizeof(cur));
while(int a=dfs(s,t,inf))
ans+=a;
}
printf("%d\n",ans);
return 0;
}
```
by SKY_magician @ 2018-06-05 11:44:25
这样也捕星$\!$~~自己去题解里看方法~~
by star_magic_young @ 2018-06-05 15:49:29