测样例的时候卡死了

accounts_somebody @ 2023-05-05 19:01:20

#include<bits/stdc++.h>
using namespace std;

const int N=205,mx=0x3f3f3f3f;
int n,m,s,t,ans,dis[N];
struct Node
{
    int to,w;
};
vector<Node>nbr[N];

bool bfs()
{
    queue<int>q;
    memset(dis,0x3f,sizeof dis);
    int cur=s;
    q.push(cur);
    dis[s]=0;
    while(!q.empty())
    {
        cur=q.front();
        q.pop();
        for(int i=0;i<nbr[cur].size();i++)
        {
            int nxt=nbr[cur][i].to,w=nbr[cur][i].w;
            if(dis[nxt]==mx&&w>0)
            {
                q.push(nxt);
                dis[nxt]=dis[cur]+1;
                if(nxt==t)
                    return true; 
            }
        }
    }
    return false;
}

int dfs(int x,int sum)
{
    if(x==t)
        return sum;
    int num=0;
    for(int i=0;i<nbr[x].size();i++)
    {
        int nxt=nbr[x][i].to,w=nbr[x][i].w;
        if(dis[x]+1==dis[nxt]&&w>0)
        {
            int val=dfs(nxt,min(sum,w));
            nbr[x][nxt].w-=val;
            nbr[nxt][x].w+=val;
            num+=val;
            sum-=val;
        }
    }
    return num;
}

int main()
{
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
        nbr[x].push_back((Node){y,w});
        nbr[y].push_back((Node){x,0});
    }
    while(bfs()==true)
    {
        ans+=dfs(s,mx);
    }
    cout<<ans;
    return 0;
}

by 2019zll @ 2023-05-05 19:20:19

反向边不是这样判断的啊，dfs 函数里面错了。

我的建议是使用链式前向星存图，边的编号从 0 或 2 开始，这样边 i 的反向边的编号就是 i \oplus 1 了。

by 2019zll @ 2023-05-05 19:22:00

当然了，对于这道题，开一个 n \times n 的二维数组存图也是可以的，只不过（如果有）重边就把边权加起来。

by 2019zll @ 2023-05-05 19:23:09

为了以后的方便（比如 10^5 个点的二分图匹配），建议使用链式前向星。

@li_bai_Delete

by accounts_somebody @ 2023-05-05 19:41:26

@2019zll 您指出了dfs的错误，但我希望您指出是哪一行，哪一个步骤来具体说明，另外，本人并没有学链式前向星，所以习惯用vector来存图。

by 2019zll @ 2023-05-05 19:55:36

nbr[x][nxt].w-=val;
nbr[nxt][x].w+=val;

这里你错以为是普通二维数组存图了。

@li_bai_Delete

by 2019zll @ 2023-05-05 19:57:37

提供我的代码

#include<cstdio>
#include<cstring>
template<typename T>
void read(T&num){
    int ch=getchar();
    num=0;
    while(ch<48||ch>57)ch=getchar();
    while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
}
template<typename T>
void write(T a){
    static int ch[20],cnt=0;
    if(a==0)putchar('0');
    while(a)ch[cnt++]=a%10|48,a/=10;
    while(cnt)putchar(ch[--cnt]);
}
template<typename T>
inline T min(const T a,const T b){
    return a<b?a:b;
}
typedef long long ll;
const int maxn=10000,maxm=100000;
const ll inf=0x7fffffffffffffff;
int n,m,s,t;
int head[maxn+1],cur[maxn+1],total=1;//total 从 1 而不是 0 开始。
struct Edge{
    int to,next,flow;
}e[maxm*2+2];
void add(const int u,const int v,const int w){
    e[++total]=Edge{v,head[u],w};//++total
    head[u]=total;
}
int dep[maxn+1];
int q[maxn+1],front,tail;
bool bfs(){
    memset(dep+1,-1,sizeof(int)*n);
    front=1,tail=0;
    q[++tail]=s;
    dep[s]=0;
    while(front<=tail){
        const int u=q[front++];
        for(int i=head[u];i;i=e[i].next){
            const int v=e[i].to;
            if(e[i].flow&&dep[v]==-1){
                dep[v]=dep[u]+1;
                q[++tail]=v;
            }
        }
    }
    return dep[t]!=-1;
}
ll dfs(const int u,ll in){
    if(u==t)return in;
    ll out=0;
    for(int&i=cur[u];i;i=e[i].next){
        const int v=e[i].to;
        if(e[i].flow&&dep[v]==dep[u]+1){
            const int res=dfs(v,min(in,(ll)e[i].flow));
            in-=res;
            out+=res;
            e[i].flow-=res;
            e[i^1].flow+=res;//反向边就是通过异或 1 实现的。
            if(!in)break;
        }
    }
    if(!out)dep[u]=-1;
    return out;
}
ll maxflow;
void dinic(){
    while(bfs()){
        memcpy(cur+1,head+1,sizeof(int)*n);
        maxflow+=dfs(s,inf);
    }
}
int main(){
    read(n),read(m),read(s),read(t);
    for(int i=1,u,v,w;i<=m;i++){
        read(u),read(v),read(w);
        add(u,v,w),add(v,u,0);
    }
    dinic();
    write(maxflow),putchar('\n');
    return 0;
}

by 2019zll @ 2023-05-05 19:59:30

如果你非要用 vector 存图，就需要对每条边存个编号，更麻烦，不如链式前向星边自带编号，建议你学一下，日子久了自然会背熟的。

by accounts_somebody @ 2023-05-05 20:39:37

@2019zll 谢谢，刚刚自学了链式前向星，我改完之后，发现还是卡死了，请您再帮忙看一看。

#include<bits/stdc++.h>
using namespace std;

const int N=205,mx=0x3f3f3f3f;
int n,m,s,t,ans,dis[N],head[N],cnt=1;
struct eg
{
    int next,to,w;
}e[N];
struct Node
{
    int to,w;
};
vector<Node>nbr[N];

void add(int v,int u,int w)
{
    e[++cnt].w=w;
    e[cnt].to=u;
    e[cnt].next=head[v];
    head[v]=cnt;
    return ;
}

bool bfs()
{
    queue<int>q;
    memset(dis,-1,sizeof dis);
    int cur=s;
    q.push(cur);
    dis[s]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=e[i].next)
        {
            int v=nbr[cur][i].to,w=nbr[cur][i].w;
            if(dis[v]==mx&&w>0)
            {
                q.push(v);
                dis[v]=dis[u]+1;
                if(v==t)
                    return true; 
            }
        }
    }
    return false;
}

int dfs(int u,int sum)
{
    if(u==t)
        return sum;
    int num=0;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to,w=e[i].w;
        if(dis[u]+1==dis[v]&&w>0)
        {
            int val=dfs(v,min(sum,w));
            e[i].w-=val;
            e[i^1].w+=val;
            num+=val;
            sum-=val;
        }
    }
    return num;
}

int main()
{
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
        add(x,y,w);
        add(y,x,0);
    }
    while(bfs()==true)
    {
        ans+=dfs(s,mx);
    }
    cout<<ans;
    return 0;
}

by 2019zll @ 2023-05-05 20:41:09

好的我看看

by 2019zll @ 2023-05-05 20:42:48

int v=nbr[cur][i].to,w=nbr[cur][i].w;

这里把 cur 改成 u！