样例没过,ISAP代码求调!
查看原帖
样例没过,ISAP代码求调!
985320
TJB_LHY楼主2025/7/1 09:55

玄学样例一直输出20

#include <bits/stdc++.h>
#define ll long long
#define U unsigned
using namespace std;
struct my_edge{
  int head[250],nex[11005],from[11005],to[11005],size;
  ll len[11005];
  void push(int u,int v,int w){
    nex[++size]=head[u];
    len[size]=w;
    from[size]=u;
    to[size]=v;
    head[u]=size;
  }
  void clear(){
    size=0;
    memset(head,0,sizeof head);
  }
}G;
ll s,t,n,m,u,v,w,dep[11005],gap[11005],now[11005],pre[11005];
void bfs(){
    memset(dep,0,sizeof dep);
    memset(gap,0,sizeof gap);
    queue<int>Q;
    Q.push(t);
    dep[t]=1;
    while(Q.size()){
        u=Q.front();Q.pop();
        gap[dep[u]]++;
        for(int i=G.head[u];i;i=G.nex[i]){
            v=G.to[i];
            if(G.len[i^1] && dep[v]==0){
                dep[v]=dep[u]+1;
                Q.push(v);
            }
        }
    }
}
ll augment(){
    ll u,v=t,flow=1e9;
    while(v!=s){
        u=pre[v];
        flow=min(G.len[u],flow);
        v=G.from[u];
    }
    v=t;
    while(v!=s){
        u=pre[v];
        G.len[u]-=flow;
        G.len[u^1]+=flow;
        v=G.from[u];
    }
    return flow;
}
void ISAP(){
    bfs();
    ll flow=0;
    int u=s,v;
    memcpy(now,G.head,sizeof G.head);
    while(dep[s]<=n){
        if(u==t){
            flow+=augment();
            u=s;
        }
        bool flag=0;
        for(int i=now[u];i;i=G.nex[i]){
            v=G.to[i];
            if(G.len[i] && dep[v]+1 == dep[u]){
                flag=1;
                pre[v]=now[u]=i;
                u=v;
                break;
            }
        }
        if(!flag){
            if(!--gap[dep[u]])break;
            ll minn=1e9;
            for(int i=G.head[u];i;i=G.nex[i]){
                v=G.to[i];
                if(minn>dep[v] && G.len[i])minn=dep[v];
            }
            dep[u]=minn+1;
            gap[dep[u]]++;
            now[u]=G.head[u];
            if(u!=s)u=G.from[pre[u]];
        }
    }
    cout<<flow;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m>>s>>t;
    while(m--){
        cin>>u>>v>>w;
        G.push(u,v,w);
        G.push(v,u,0);
    }
    ISAP();
	return 0;
}
2025/7/1 09:55
加载中...