U562065 网路流相关代码
题目背景
# 最大流
## Dinic
### 朴素Dinic
```cpp
bool bfs(){
for(int i=1;i0&&dep[v]==0){
dep[v]=dep[x]+1;
if(v==t){
return 1;
}
q.push(v);
}
}
}
return 0;
}
int dfs(int x,int flow){
if(x==t) return flow;
int rest=flow;
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].to,w=e[i].w;
if(w>0&&dep[v]==dep[x]+1){
int t=dfs(v,min(rest,w));
rest-=t;
e[i].w-=t;
e[i^1].w+=t;
}
}
return flow-rest;
}
```
### 完全体 Dinic
```cpp
bool bfs(){
for(int i=1;i0&&dep[v]==0){
dep[v]=dep[x]+1;
if(v==t){
return 1;
}
q.push(v);
}
}
}
return 0;
}
int dfs(int x,int flow){
if(x==t) return flow;
int rest=flow;
for(int i=lead[x];i&&rest;i=e[i].nxt){
lead[x]=i;
int v=e[i].to,w=e[i].w;
if(w>0&&dep[v]==dep[x]+1){
int t=dfs(v,min(rest,w));
if(!t) dep[v]=0;
rest-=t;
e[i].w-=t;
e[i^1].w+=t;
}
}
return flow-rest;
}
```
## ISAP
```cpp
void bfs(){
while(!q.empty()) q.pop();
q.push(t);
dep[t]=1;
gap[1]++;
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].to;
if(!dep[v]){
dep[v]=dep[x]+1;
q.push(v);
gap[dep[v]]++;
}
}
}
}
int dfs(int x,int flow){
if(x==t||flow==0) return flow;
int rest=flow;
for(int i=lead[x];i&&rest;i=e[i].nxt){
lead[x]=i;
int v=e[i].to,w=e[i].w;
if(dep[x]==dep[v]+1&&w>0){
int t=dfs(v,min(rest,w));
rest-=t;
e[i].w-=t;
e[i^1].w+=t;
}
}
if(rest){
gap[dep[x]]--;
if(!gap[dep[x]]){
dep[s]=t+1;
}
dep[x]++;
gap[dep[x]]++;
}
return flow-rest;
}
int ISAP(){
int ans=0;
memset(dep,0,sizeof(dep));
memset(gap,0,sizeof(gap));
bfs();
while(dep[s]
题目描述
# 费用流
## Dinic求费用流
没打过拷了个 tj。
```cpp
bool spfa()//spfa求最短路
{
memset(Dis,0x3f,sizeof(Dis));
memset(Vis,0,sizeof(Vis));
memcpy(Cur,Head,sizeof(Cur));
Q.clear();
Q.push_back(s);
Dis[s]=0;
Vis[s]=1;
while(!Q.empty())
{
int x=Q.front();
Q.pop_front();
Vis[x]=0;
for(int i=Head[x];i;i=Next[i])
{
int y=Son[i];
if(Cap[i]&&Dis[y]>Dis[x]+Cost[i])
{
Dis[y]=Dis[x]+Cost[i];
if(!Vis[y])
{
Q.push_back(y);
Vis[y]=1;
}
}
}
}
return Dis[t]^infll;
}
ll dfs(int x,ll flow)//dfs增广
{
if(x==t)return flow;
Vis[x]=1;
ll res=0;
for(int i=Cur[x];i&&flow;i=Next[i])
{
int y=Son[i];
Cur[x]=i;
if(!Vis[y]&&Cap[i]&&Dis[y]==Dis[x]+Cost[i])
{
ll k=dfs(y,min(flow,Cap[i]));
if(!k)Dis[y]=infll;
Cap[i]-=k;
Cap[i^1]+=k;
res+=k;
flow-=k;
mincost+=k*Cost[i];//直接在这里记录费用
}
}
Vis[x]=0;
return res;
}
```
## EK 求费用流
```cpp
bool spfa(){
for(int i=1;i
输入格式
# 上下界网络流
## 满配
省略了前面的原始对偶，给你个满配你还不磕俩响头（？）
```cpp
void add(int u,int v,int l,int r,int c){
//注意这个是传5个参数的，参与流量计算
add(u,v,r-l,c);
liu[u]-=l,liu[v]+=l;
}
//注意下边的所有都只有4个参，不参与流量计算
add(yt,ys,1e18,0);
//如果无源汇则不需要这一行，这条边的编号会被 nb 记录。
for(int i=1;i0){
add(s,i,liu[i],0);
all+=liu[i];
}
else if(liu[i]
输出格式
无