AfterFullStop @ 2023-08-04 22:13:50
这是一份#10会TLE的代码:
#include<bits/stdc++.h>
#define ri register int
#define ll long long
using namespace std;
const ll maxn=2e2+5,maxm=1e4+5,inf=2147483647;
int n,m,s,t;
int cnt,head[maxn],nxt[maxm],to[maxm];
ll bq[maxm];
void add(int u,int v,int w){
++cnt;
to[cnt]=v;
nxt[cnt]=head[u];
bq[cnt]=w;
head[u]=cnt;
}
int flag[maxn][maxn];
ll flow;
ll dis[maxn],pre[maxn];
bool vis[maxn];
bool bfs(){
memset(vis,0,sizeof(vis));
for(ri i=1;i<=n;i++)dis[i]=inf;
memset(pre,0,sizeof(pre));
queue<int>q;
q.push(s);
vis[s]=1;
while(!q.empty()){
int u=q.front();q.pop();
for(ri e=head[u];e;e=nxt[e]){
int v=to[e];
ll w=bq[e];
if(!w||vis[v])continue;
pre[v]=u;
dis[v]=min(dis[u],w);
vis[v]=1;
q.push(v);
if(v==t)return 1;
}
}return 0;
}
void update(){
int v=t;
while(v^s){
int u=pre[v];int b=flag[u][v];
bq[b]-=dis[t];bq[b^1]+=dis[t];
v=u;
}flow+=dis[t];
}
void EK(){
while(bfs()){
update();
}
}
signed main(){
//freopen("lg.in","r",stdin);
//freopen("lg.out","w",stdout);
ios::sync_with_stdio(0);
cin>>n>>m>>s>>t;
cnt=1;
for(ri i=1,u,v,w;i<=m;i++){
cin>>u>>v>>w;
if(flag[u][v]){
bq[flag[u][v]]+=w;
}else{
add(u,v,w);
flag[u][v]=cnt;
add(v,u,0);
}
}
EK();
cout<<flow;
//fclose(stdout);
return 0;
}
可是当我把 if(!w||vis[v])continue;
改成 if(w<=0||vis[v])continue;
时,居然神奇的AC了
这也就意味着有w是负的,但是似乎没有一个地方会把w变负,于是就蒙圈了。
本来想着可能是炸了int,结果define了还是TLE
哪位大佬能解释一下?谢谢
by _Haoomff_ @ 2023-08-05 08:00:43
@ChrysanthBlossom 我感觉不是的,!w 表示的是 w 不为 0,那么也就可以为正数,正数的时候 continue……
by AfterFullStop @ 2023-08-05 08:04:51
@Haoomff 可是我把!w改成w==0照样会T(
by _Haoomff_ @ 2023-08-05 08:06:11
@ChrysanthBlossom 说明会出现负数
bq[b]-=dis[t];
这步可能会减出负吧
by AfterFullStop @ 2023-08-05 08:14:21
@Haoomff
可是理论上来说bq[e]应该比dis[t]要大啊。
照这样看可能是flag整错了,但好像也没问题啊
by 阿丑 @ 2023-08-05 08:20:10
反向边也要赋 flag
(
by AfterFullStop @ 2023-08-05 08:39:41
@阿丑 谢谢,wssb