(他本人被禁言了)
by 1lgorithm @ 2021-11-25 13:28:41
TM是真的强
by herselfqwq @ 2021-11-25 13:40:08
代码:
```cpp
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<cmath>
using namespace std;
inline int read(){
int s=0;
char c=getchar();
while(!isdigit(c)){
c=getchar();
}
while(isdigit(c)){
s=(s<<3)+(s<<1)+(c^48);
c=getchar();
}
return s;
}
struct g{
int t,w,cd;
}sz[120005];
struct node{
int w,cd,syg;
}lsqxx[600005];
inline int px(const register struct g a1,const register struct g a2){
return a1.cd>a2.cd;
}
int ans,head[120005],tou[120005];
int n,m,s,t,daan;
inline void add(const register int t,const register int w,const register int cd){
ans+=2;
lsqxx[ans].w=w;
lsqxx[ans].cd=cd;
lsqxx[ans].syg=head[t];
head[t]=ans;
}
inline void addf(const register int t,const register int w){
ans+=2;
lsqxx[ans].w=w;
lsqxx[ans].syg=head[t];
head[t]=ans;
}
int dep[1205];
queue<int>q;
inline int bfs(){
memset(dep,-1,sizeof(dep));
dep[s]=0;
q.push(s);
while(!q.empty()){
int now=q.front();
q.pop();
for(int i=head[now];i;i=lsqxx[i].syg){
if(lsqxx[i].cd&&dep[lsqxx[i].w]==-1){
dep[lsqxx[i].w]=dep[now]+1;
q.push(lsqxx[i].w);
}
}
}
return dep[t]!=-1;
}
inline int dfs(const register int top,register int jin){
if(top==t){
return jin;
}
int chu=0;
for(int i=tou[top];i;i=lsqxx[i].syg){
if(lsqxx[i].cd&&dep[lsqxx[i].w]==dep[top]+1){
int shu=dfs(lsqxx[i].w,min(jin,lsqxx[i].cd));
lsqxx[i].cd-=shu;
lsqxx[i^1].cd+=shu;
jin-=shu;
chu+=shu;
if(!jin){
tou[top]=i;
return chu;
}
}
}
tou[top]=0;
return chu;
}
int main(){
register int i,j,wz;
n=read(),m=read(),s=read(),t=read();
for(i=1;i<=m;++i){
sz[i].t=read(),sz[i].w=read(),sz[i].cd=read();
}
sort(sz+1,sz+1+m,px);
for(i=0;i<2;++i){
if(i==1){
ans=1;
}
for(j=7,wz=1;j>=0;j--){
while(wz<=m&&sz[wz].cd>=(1<<(j*4))){
if(!i){
add(sz[wz].t,sz[wz].w,sz[wz].cd);
}else{
addf(sz[wz].w,sz[wz].t);
}
wz++;
}
while(bfs()){
memcpy(tou,head,sizeof(tou));
daan+=dfs(s,2147483647);
}
}
}
printf("%d",daan);
return 0;
}
```
by 1lgorithm @ 2021-11-26 18:15:30
草,@[oscar](/user/3346)
by DaShaber @ 2021-12-12 21:42:52
草,@[oscar](/user/3346)
by _l_l_ @ 2022-01-01 08:27:54