问关于 long long,玄关
查看原帖
问关于 long long,玄关
654577
RainySoul楼主2025/1/13 15:30

为什么下面这份代码去掉 #define int long long 是 68pts,开了 long long 之后会死循环呢?问解决方案

另:并非 inf\inf 开小了

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
using namespace std;
const int N=210;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct zyx{
    int to,w;
};
vector<zyx> e[N];
queue<int> q;
int n,m,s,t,start[N],depth[N];
void init(){
    memset(depth,inf,sizeof depth);
    memset(start,0,sizeof start);
}
bool bfs(){
    init();
    q.push(s);
    depth[s]=0;
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(int i=0;i<(int)e[now].size();i++){
            int to=e[now][i].to;
            if(depth[to]!=inf||e[now][i].w<=0)continue;
            q.push(to);
            depth[to]=depth[now]+1;
        }
    }
    return (depth[t]!=inf);
}
int dfs(int now,int W){
    if(now==t)return W;
    for(int i=start[now];i<(int)e[now].size();i++){
        start[now]=i;
        int to=e[now][i].to;
        if(e[now][i].w>0&&(depth[to]==depth[now]+1)){
            int temp=dfs(to,min(W,e[now][i].w));
            if(temp==0){
                depth[to]=inf;
            }
            else{
                e[now][i].w-=temp;
                bool flag=0;
                for(int j=0;j<(int)e[to].size();j++){
                    if(e[to][j].to==now){
                        e[to][j].w+=temp;
                        flag=1;
                        break;
                    }
                }
                if(flag==0)e[to].push_back((zyx){now,temp});
                return temp;
            }
        }
    }
    return 0;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    n=read(),m=read(),s=read(),t=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read(),w=read();
        e[u].push_back((zyx){v,w});
    }
    int ans=0;
    while(bfs())ans+=dfs(s,inf);
    cout<<ans;
    return 0;
}
2025/1/13 15:30
加载中...