这是一份#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
哪位大佬能解释一下?谢谢