测样例的时候卡死了

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 20:43:36

干脆不定义 cur 这个变量了。

by accounts_somebody @ 2023-05-05 20:49:42

OK，改完之后变成答案0了。。。（我太弱了）

by accounts_somebody @ 2023-05-05 20:49:54

@2019zll

by 2019zll @ 2023-05-05 20:51:28

手机上查看不方便，请见谅

by 2019zll @ 2023-05-05 21:01:39

好了过了

一 流量开 long long，注意数据范围！

二 把不用的 vector 删掉！

三 如果流完这次已经没有流量了，break。

四 如果这个点流不出去，dis[u]=1。

五 最好用上当前弧优化（我没写）。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=205,M=5000;
const ll mx=0x3f3f3f3f3f3f3f3f;
int n,m,s,t,dis[N],head[N],cnt=1;
struct eg
{
    int next,to,w;
}e[M*2+2];
struct Node
{
    int to,w;
};
ll ans;

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);
    q.push(s);
    dis[s]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to,w=e[i].w;
            if(dis[v]==-1&&w>0)
            {
                q.push(v);
                dis[v]=dis[u]+1;
            }
        }
    }
    return dis[t]!=-1;
}

ll dfs(int u,ll sum)
{
    if(u==t)
        return sum;
    ll 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,(ll)w));
            e[i].w-=val;
            e[i^1].w+=val;
            num+=val;
            sum-=val;
            if(!sum)break;
        }
    }
    if(!num)dis[u]=-1;
    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 21:02:15

@li_bai_Delete

手机码字好累啊……

by 2019zll @ 2023-05-05 21:03:18

你可以比对两份代码针对性学习一下。

by 2019zll @ 2023-05-05 21:05:28

• dis[u]=-1