1 条题解
-
0
hetao8552981 LV 6 @ 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%
- 上传者