王茗仟 @ 2022-11-04 20:28:48
#define int long long
#define re register
#define in inline
#define max(a,b) ((a)>(b)?a:b)
#define min(a,b) ((a)<(b)?a:b)
using namespace std;
const int MAXN=1e4+10;
const int MAXM=2e5+19;
const int INF=0x3f3f3f3f3f;
in int read(){
re int x=0,f=0;re char c=getchar();
while(!isdigit(c)) f|=(c=='-'),c=getchar();
while(isdigit(c)) x=(x<<3)+(x<<1)+c-'0',c=getchar();
return f?-x:x;
}
int n,m,s,t,dis[MAXN],cur[MAXN];
struct edge{
int u,v,w;
int nx;
}e[MAXM];
int head[MAXN],tot;
in void add(int u,int v,int w){
e[tot].u=u;
e[tot].v=v;
e[tot].w=w;
e[tot].nx=head[u];
head[u]=tot++;
}
bool bfs(){
//广搜一下测一下剩下点的深度,顺便找出增广路
queue<int>q;
memset(dis,-1,sizeof(dis));
q.push(s);
dis[s]=0;
cur[s]=head[s];//cur是当前弧优化的宝贝
while(q.size()){
int u=q.front();
q.pop();
for(int i=head[u];~i;i=e[i].nx){
int v=e[i].v;
if(dis[v]==-1&&e[i].w){
dis[v]=dis[u]+1;
cur[v]=head[v];
if(v==t){
return 1;
}
q.push(v);
}
}
}
return 0;//不存在增广路了,可以结束le
}
int dfs(int u,int lim){
// 当前节点 能增加的最大流量
//深搜??也就是增广一下,给下流
if(u==t){
return lim;
}
int flow=0;//从u点分出去的
for(int i=cur[u];~i;i=e[i].nx){
cur[i]=i;//当前弧优化,很新对你来说,(走过就不再走了)
int v=e[i].v;
if(dis[v]==dis[u]+1&&e[i].w){
int minf=dfs(v,min(e[i].w,lim-flow));//求要给v多少
//limit-flow给这条边能分的最多有多少
e[i].w-=minf;
e[i^1].w+=minf;
flow+=minf;
if(flow==lim){
//全分完了直接结束吧
return flow;
}
}
}
return flow;
}
int dinic(){
int ans=0;
while(bfs()){
// cout<<ans<<endl;
ans+=dfs(s,INF);
}
return ans;
}
signed main(){
n=read();m=read();s=read();t=read();
memset(head,-1,sizeof(head));
for(re int i=1;i<=m;i++){
int u,v,w;
u=read();v=read();w=read();
add(u,v,w);add(v,u,0);
}
cout<<dinic()<<endl;
return 0;
}
by 王茗仟 @ 2022-11-04 20:29:09
他是怎样陷入无限循环的
by treeqwq @ 2022-11-04 20:31:34
加了当前弧优化就必须改成
for(int i=cur[u];~i&&flow<lim;i=e[i].nx){
cur[i]=i;//当前弧优化,很新对你来说,(走过就不再走了)
int v=e[i].v;
if(dis[v]==dis[u]+1&&e[i].w){
int minf=dfs(v,min(e[i].w,lim-flow));//求要给v多少
//limit-flow给这条边能分的最多有多少
e[i].w-=minf;
e[i^1].w+=minf;
flow+=minf;
if(flow==lim){
//全分完了直接结束吧
return flow;
}
}
}
要不然 cur 会一直更新
by treeqwq @ 2022-11-04 20:31:44
@王茗仟
by IceYukino @ 2022-11-04 20:35:25
没看出来您改了啥?
by 王茗仟 @ 2022-11-04 20:35:55
@LSOT
您是不是只改了for里面那一点
by treeqwq @ 2022-11-04 20:36:20
@王茗仟 对
by 王茗仟 @ 2022-11-04 20:37:42
@LSOT
并不是那里的问题
by 王茗仟 @ 2022-11-04 20:38:46
@gqh_juruo
他改了for的条件
by 野生林登万 @ 2022-11-04 20:39:01
您的for(int i=head[u];~i;i=e[i].nx)
为什么不写成for(int i=head[u];i;i=e[i].nx)
呢?咱不知道为什么要写~i
修改以后答案依然不对,但是不会TLE了,另外,可以增加剪枝:
if(u==t || lim == 0){
return lim;
}
by treeqwq @ 2022-11-04 20:39:13
@王茗仟 啊,那就不知道了,不过你不该这里也过不去(((