73 wa3个点

wenxutong @ 2023-01-27 10:45:10

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxx 200000000000000000LL
struct point{
    ll x,step;
};
ll n,m,s,t;
ll g[205][205],cen[205],cnt[205];
ll ans=0;
point q[1040005];
bool bfs(){
    memset(cen,-1,sizeof(cen));
    q[1].x=s,q[1].step=1;
    ll f=1,e=1;
    while(f<=e){
        point u=q[f];
        f++;
        if(cen[u.x]!=-1)continue;
        cen[u.x]=u.step;
        for(ll i=1;i<=n;i++){
            if(g[u.x][i]>0&&cen[i]==-1){
                e++;
                q[e].x=i,q[e].step=u.step+1;
            }
        }
    }
    if(cen[t]==-1)return 0;
    return 1;
}
ll dfs(ll now,ll val){
    if(now==t)return val;
    for(ll i=1;i<=n;i++){
        if(g[now][i]>0&&cen[i]==cen[now]+1){
            ll jia=dfs(i,min(val,g[now][i]));
            if(jia>0){
                g[now][i]-=jia;
                g[i][now]+=jia;
                return jia;
            }
        }
    }
    return 0;
}
void dinic(){
    while(1){
        bool flag=bfs();
        if(flag==0)break;
        while(1){
            ll jia=dfs(s,maxx);
            ans+=jia;
            if(jia==0)break;
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>s>>t;
    memset(g,0,sizeof(g));
    for(ll i=1;i<=m;i++){
        ll xx,yy,vv;
        cin>>xx>>yy>>vv;
        g[xx][yy]=vv;
    }
    dinic();
    cout<<ans<<"\n";
    return 0;
}

by TheSky233 @ 2023-01-27 11:34:07

@wenxutong 首先这个图可能有重边，所以不能用邻接矩阵存图，得用前向星或 vector（个人喜好前向星）

我帮你改了下前向星，record，#9 T 了，得用当前弧或多路增广优化

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxx 200000000000000000LL
struct point{
    int x,step;
};
struct edge{
    ll to,w,nxt;
}e[10005];
int head[205],cnt=1;
void addedge(int u,int v,int w){
    e[++cnt]={v,w,head[u]}; head[u]=cnt;
}
int n,m,s,t;
ll cen[205];
ll ans=0;
point q[10040005];
bool bfs(){
    memset(cen,-1,sizeof(cen));
    q[1].x=s,q[1].step=1;
    int f=1,ed=1;
    while(f<=ed){
        point u=q[f];
        f++;
        if(cen[u.x]!=-1)continue;
        cen[u.x]=u.step;
        for(int i=head[u.x];i;i=e[i].nxt){
            int t=e[i].to;
            if(e[i].w>0&&cen[t]==-1){
                ed++;
                q[ed].x=t,q[ed].step=u.step+1;
            }
        }
    }
    return (cen[t]!=-1);
}
ll dfs(int now,ll val){
    if(now==t)return val;
    for(int i=head[now];i;i=e[i].nxt){
        int t=e[i].to;
        if(e[i].w>0&&cen[t]==cen[now]+1){
            ll jia=dfs(t,min(val,e[i].w));
            if(jia>0){
                e[i].w-=jia;
                e[i^1].w+=jia;
                return jia; 
            }
        }
    }
    return 0;
}
void dinic(){
    while(1){
        bool flag=bfs();
        if(flag==0)break;
        while(1){
            ll jia=dfs(s,maxx);
            if(jia==0)break;
            ans+=jia;
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        int xx,yy,vv;
        cin>>xx>>yy>>vv;
        addedge(xx,yy,vv);
        addedge(yy,xx,0);
    }
    dinic();
    cout<<ans<<"\n";
    return 0;
}

by wenxutong @ 2023-01-27 11:41:41

@TheSky233 谢谢大佬，我知道了

by wenxutong @ 2023-01-27 13:31:31

@TheSky233

此贴终结，我调好了，还是用邻接矩阵，有重边就直接把边权加上去

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxx 200000000000000000LL
struct point{
    ll x,step;
};
ll n,m,s,t;
ll g[205][205],cen[205],cnt[205];
ll ans=0;
point q[1040005];
bool bfs(){
    memset(cen,-1,sizeof(cen));
    q[1].x=s,q[1].step=1;
    ll f=1,e=1;
    while(f<=e){
        point u=q[f];
        f++;
        if(cen[u.x]!=-1)continue;
        cen[u.x]=u.step;
        for(ll i=1;i<=n;i++){
            if(g[u.x][i]>0&&cen[i]==-1){
                e++;
                q[e].x=i,q[e].step=u.step+1;
            }
        }
    }
    if(cen[t]==-1)return 0;
    return 1;
}
ll dfs(ll now,ll val){
    if(now==t)return val;
    for(ll i=1;i<=n;i++){
        if(g[now][i]>0&&cen[i]==cen[now]+1){
            ll jia=dfs(i,min(val,g[now][i]));
            if(jia>0){
                g[now][i]-=jia;
                g[i][now]+=jia;
                return jia;
            }
        }
    }
    return 0;
}
void dinic(){
    while(1){
        bool flag=bfs();
        if(flag==0)break;
        while(1){
            ll jia=dfs(s,maxx);
            ans+=jia;
            if(jia==0)break;
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>s>>t;
    memset(g,0,sizeof(g));
    for(ll i=1;i<=m;i++){
        ll xx,yy,vv;
        cin>>xx>>yy>>vv;
        g[xx][yy]+=vv;
    }
    dinic();
    cout<<ans<<"\n";
    return 0;
}