1 条题解

  • 0
    @ 2025-06-26 05:56:13
    #include<bits/stdc++.h>
    using namespace std;
    const int N=2e4+5,M=2e5+5,inf=0x3f3f3f3f;
    int n,s,t,tot;
    int v[M<<1],w[M<<1],first[N],nxt[M<<1];
    int h[N],e[N],gap[N<<1],inq[N];
    struct cmp
    {
        inline bool operator()(int a,int b) const
        {
            return h[a]<h[b];
        }
    };
    queue<int> Q;
    priority_queue<int,vector<int>,cmp> pQ;
    inline void add_edge(int from,int to,int flow)
    {
        tot+=2;
        v[tot+1]=from;v[tot]=to;w[tot]=flow;w[tot+1]=0;
        nxt[tot]=first[from];first[from]=tot;
        nxt[tot+1]=first[to];first[to]=tot+1;
        return;
    }
    inline bool bfs()
    {
        int now;
        int go;
        memset(h+1,0x3f,sizeof(int)*n);
        h[t]=0;Q.push(t);
        while(!Q.empty())
        {
            now=Q.front();Q.pop();
            for(go=first[now];go;go=nxt[go])
                if(w[go^1]&&h[v[go]]>h[now]+1)
                    h[v[go]]=h[now]+1,Q.push(v[go]);
        }
        return h[s]!=inf;
    }
    inline void push(int now)
    {
        int d;
        int go;
        for(go=first[now];go;go=nxt[go])
            if(w[go]&&h[v[go]]+1==h[now])
            {
                d=min(e[now],w[go]);
                w[go]-=d;w[go^1]+=d;e[now]-=d;e[v[go]]+=d;
                if(v[go]!=s&&v[go]!=t&&!inq[v[go]])
                    pQ.push(v[go]),inq[v[go]]=1;
                if(!e[now])
                    break;
            }
        return;
    }
    inline void relabel(int now)
    {
        int go;
        h[now]=inf;
        for(go=first[now];go;go=nxt[go])
            if(w[go]&&h[v[go]]+1<h[now])
                h[now]=h[v[go]]+1;
        return;
    }
    inline int hlpp()
    {
        int now,d;
        register int i,go;
        if(!bfs())
            return 0;
        h[s]=n;
        memset(gap,0,sizeof(int)*(n<<1));
        for(i=1;i<=n;i++)
            if(h[i]<inf)
                ++gap[h[i]];
        for(go=first[s];go;go=nxt[go])
            if(d=w[go])
            {
                w[go]-=d;w[go^1]+=d;e[s]-=d;e[v[go]]+=d;
                if(v[go]!=s&&v[go]!=t&&!inq[v[go]])
                    pQ.push(v[go]),inq[v[go]]=1;
            }
        while(!pQ.empty())
        {
            inq[now=pQ.top()]=0;pQ.pop();push(now);
            if(e[now])
            {
                if(!--gap[h[now]])
                    for(i=1;i<=n;i++)
                        if(i!=s&&i!=t&&h[i]>h[now]&&h[i]<n+1)
                            h[i]=n+1;
                relabel(now);++gap[h[now]];
                pQ.push(now);inq[now]=1;
            }
        }
        return e[t];
    }
    int m;
    signed main()
    {
        int x,y;
        cin>>x>>y;
        n=4,m=4,s=1,t=4;
        add_edge(1,2,x);
        add_edge(1,3,y);
        add_edge(2,4,10000000);
        add_edge(3,4,10000000);
        printf("%d\n",hlpp());
        return 0;
    }
    ```cpp
    还有一种是:
    ```cpp
    print(sum(map(int, input().split()))#python
    
  • 1

信息

ID
1000
难度
1
分类
(无)
标签
(无)
递交数
7
已通过
4
通过率
57%
上传者