https://ac.nowcoder.com/acm/problem/25875

# 有源汇的有上下界的最大流

## 完整代码（此题的）

```#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int x=0;
char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return x;
}
const int mx=1e6;
const int inf=1<<30;
int n,m;
int s,t,ss,tt;
int top=1;
int cur[mx];
struct Edge{
int v;
int val;
int next;
}edge[mx<<1];
edge[++top].v=v;
edge[top].val=val;
}
}
bool inque[mx];
int deep[mx];
bool spfa(int s,int t){
queue<int>q;
q.push(s);
deep[s]=0;
while(!q.empty()){
int u=q.front();
q.pop();
inque[u]=0;
if(!edge[i].val)continue;
int v=edge[i].v;
if(deep[v]>deep[u]+1){
deep[v]=deep[u]+1;
if(!inque[v]&&v!=t){
q.push(v);
inque[v]=1;
}
}
}
}
return deep[t]!=inf;
}
int dfs(int flow,int u,int t){
if(u==t)return flow;
int used=0;
for(int i=cur[u];i;i=edge[i].next){
cur[u]=i;
if(!edge[i].val)continue;
int v=edge[i].v;
if(deep[v]==deep[u]+1){
int now=dfs(min(edge[i].val,flow-used),v,t);
used+=now;
edge[i].val-=now;
edge[i^1].val+=now;
if(used==flow)return flow;
}
}
return used;
}
int Dinic(int s,int t){
int maxflow=0;
while(spfa(s,t)){
maxflow+=dfs(inf,s,t);
}
return maxflow;
}
int d[mx];//每个点的流量（最小入流量-最小出流量）
int main(){
ss=n+1,tt=n+2;//新的起点和终点
for(int i=1;i<=m;++i){
d[u]-=low;
d[v]+=low;
}
int flow=0;//满流应该的流量
for(int i=1;i<=n;++i){
}
int k=Dinic(ss,tt);
if(k!=flow){//不可行
return 0;
}
printf("%d",Dinic(s,t));
return 0;
}```

2022-12-27 18:33

2022-12-31 14:41

2022-12-19 18:55

2022-12-24 16:00

2022-12-19 17:47

2022-12-22 00:27

2022-12-14 12:09

2022-12-15 15:13

2022-12-28 01:03

2022-12-24 15:47