# #115. 无源汇有上下界可行流

#### 描述

n n n 个点，m m m 条边，每条边 e e e 有一个流量下界 lower(e) \text{lower}(e) lower(e) 和流量上界 upper(e) \text{upper}(e) upper(e)，求一种可行方案使得在所有点满足流量平衡条件的前提下，所有边满足流量限制。

#### 样例输入 1

4 6
1 2 1 2
2 3 1 2
3 4 1 2
4 1 1 2
1 3 1 2
4 2 1 2

#### 样例输出 1

NO

#### 样例输入 2

4 6
1 2 1 3
2 3 1 3
3 4 1 3
4 1 1 3
1 3 1 3
4 2 1 3

#### 样例输出 2

YES
1
2
3
2
1
1

#### 数据范围与提示

1≤n≤200,1≤m≤10200 1 \leq n \leq 200, 1 \leq m \leq 10200 1≤n≤200,1≤m≤10200

#### 显示分类标签

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int MAXN=2000001;
inline char nc()
{
static char buf[MAXN],*p1=buf,*p2=buf;
}
{
char c=nc();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}
return x*f;
}
int n,m,s,t;
struct node
{
int u,v,flow,nxt;
}edge[MAXN];
int num=0;
{
edge[num].u=x;
edge[num].v=y;
edge[num].flow=z;
}
{
}
int deep[MAXN],L[MAXN];
bool BFS()
{
memset(deep,0,sizeof(deep));
deep[s]=1;
queue<int>q;
q.push(s);
while(q.size()!=0)
{
int p=q.front();
q.pop();
if(!deep[edge[i].v]&&edge[i].flow)
{
deep[edge[i].v]=deep[edge[i].u]+1;q.push(edge[i].v);
if(edge[i].v==t) return 1;
}

}
return deep[t];

}
int DFS(int now,int nowflow)
{
if(now==t||nowflow<=0)
return nowflow;
int totflow=0;
for(int &i=cur[now];i!=-1;i=edge[i].nxt)
{
if(deep[edge[i].v]==deep[edge[i].u]+1&&edge[i].flow)
{
int canflow=DFS(edge[i].v,min(nowflow,edge[i].flow));
edge[i].flow-=canflow;
edge[i^1].flow+=canflow;
totflow+=canflow;
nowflow-=canflow;
if(nowflow<=0)
break;
}
}
}
int Dinic()
{
int ans=0;
while(BFS())
{
for(int i=0;i<=n;i++)
ans+=DFS(s,1e8);
}
return ans;
}
int main()
{
#ifdef WIN32
freopen("a.in","r",stdin);
#else
#endif
for(int i=1;i<=m;i++)
{
}
int sum=0;
for(int i=1;i<=n;i++)
{
}
if(Dinic()!=sum) printf("NO");
else
{
printf("YES\n");
for(int i=0;i<m;i++)
printf("%d\n",edge[i*2|1].flow+L[i]);
}
return  0;
}

1811 篇文章114 人订阅

0 条评论

## 相关文章

1533

1655

1954

1969

### POJ1201 Intervals(差分约束)

Description You are given n closed, integer intervals [ai, bi] and n integers c1...

2768

52710

1412

### 建模常用的pandas语句

pandas对象是Python常用的数据分析模块，它主要包括series对象，dataframe对象和index对象。每种对象都有自己所特有的方法和属性。今...

330

822

984