# 样例没过却AC了

P3376 【模板】网络最大流

蓝莲花__ @ 2019-10-11 16:16:44

样例没过却AC了

求助大佬看代码!!!

#include<bits/stdc++.h>
using namespace std;
const int mx=100010,MAX=1e9;
int n,m,s,t,tot=-1;
int h[mx],d[mx],cur[mx];
struct node{int nxt,to,w;}e[mx<<1];
queue<int> q;
void add(int x,int y,int cc)
{
    e[++tot].nxt=h[x];
    e[tot].to=y;
    e[tot].w=cc;
    h[x]=tot;
}
bool bfs()
{
    for (int i=1;i<=n;i++) d[i]=-1,cur[i]=h[i];
    d[s]=1;q.push(s);
    while (!q.empty())
    {
        int x=q.front();
        q.pop();
        for (int i=h[x];i;i=e[i].nxt)
        {
            int y=e[i].to;
            if (d[y]==-1 && e[i].w)
            {
                d[y]=d[x]+1;
                q.push(y);
            }
        }
    }
    if (d[t]==-1) return false;
    return true;
}
int dfs(int x,int lim)
{
    if (x==t || lim==0) return lim;
    int flow=0,f;
    for (int i=cur[x];i;i=e[i].nxt)
    {
        cur[x]=i;
        int y=e[i].to;
        if (d[y]==d[x]+1 && e[i].w)
        {
            f=dfs(y,min(lim,e[i].w));
            flow+=f;
            lim-=f;
            e[i].w-=f;
            e[i^1].w+=f;
            if (!lim) break;
        }
    }
    return flow;
}
int main()
{
    cin>>n>>m>>s>>t;
    for (int i=1;i<=m;i++)
    {
        int x,y,cc;
        cin>>x>>y>>cc;
        add(x,y,cc);
        add(y,x,0);
    }
    int ans=0;
    while (bfs()) ans+=dfs(s,MAX);
    cout<<ans;
    return 0;
}
/*
10 25 3 1
9 3 80
5 10 62
4 2 13
7 2 20
3 10 90
6 10 53
2 3 11
6 3 45
9 5 37
10 9 93
7 8 28
4 5 28
1 2 52
4 5 54
1 2 62
7 4 64
4 3 40
7 3 39
8 2 72
7 5 5
3 6 88
3 2 56
9 2 72
2 1 81
6 7 84

*/

by wmy_goes_to_thu @ 2019-10-11 16:20:47

正常,比如一道题叫做大吉大利,晚上吃鸡


by wmy_goes_to_thu @ 2019-10-11 16:21:09

P4061


by 莫奈的崖径 @ 2019-10-11 16:29:24

我只能说tql


|