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

内存限制：256 MiB时间限制：1000 ms标准输入输出

题目类型：传统评测方式：Special Judge

上传者：匿名

题目描述

这是一道模板题。

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

输入格式

第一行两个正整数 n nn、m mm。

之后的 m mm 行，每行四个整数 s ss、t tt、lower \text{lower}lower、upper \text{upper}upper。

输出格式

如果无解，输出一行 NO。

否则第一行输出 YES，之后 m mm 行每行一个整数，表示每条边的流量。

样例

样例输入 1

样例输出 1

NO

样例输入 2

样例输出 2

数据范围与提示

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

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 #define maxm 12000

 #define maxn 500

 using namespace std;

 int read() {

     int x=,f=;char ch=getchar();

     while(!isdigit(ch)){ch=getchar();}

     while(isdigit(ch)){x=x*+ch-'';ch=getchar();}

     return x;

 }

 struct data {

     int to,next,w,f;

 }e[maxm*];

 int head[maxn],cnt;

 int cur[maxn];

 void add(int u,int v,int w,int f){e[cnt].next=head[u];e[cnt].to=v;e[cnt].w=w;e[cnt].f=f;head[u]=cnt++;}

 int n,m,s,t;

 int q[maxn];

 bool vis[maxn];

 int dis[maxn];

 bool bfs() {

     memset(dis,-,sizeof(dis));

     int h=,tt=;

     q[h]=t;

     vis[t]=;

     dis[t]=;

     while(h!=tt) {

         int now=q[h];h++;vis[now]=;if(h==maxn) h=;

         for(int i=head[now];i>=;i=e[i].next) {

             int to=e[i].to;

             if(e[i^].w&&dis[to]<-) {

                 dis[to]=dis[now]-;

                 if(!vis[to]){

                     vis[to]=;

                     q[tt++]=to;if(tt==maxn) tt=;

                 }

             }

         }

     }

     return dis[s]>=-;

 }

 int dfs(int now,int a) {

     if(now==t||a==) return a;

     int flow=,f;

     for(int i=cur[now];i>=;i=e[i].next) {

         int to=e[i].to;

         if(dis[to]==dis[now]+&&e[i].w>&&(f=dfs(to,min(a,e[i].w)))) {

             e[i].w-=f;

             e[i^].w+=f;

             flow+=f;

             a-=f;

             if(a==) return flow;

         }

         cur[now]=i;

     }

     if(!flow) dis[now]=-;

     return flow;

 }

 int main() {

     memset(head,-,sizeof(head));

     n=read(),m=read(),s=,t=n+;

     int tot=;

     for(int i=;i<=m;i++) {

         int u=read(),v=read(),lw=read(),w=read();

         tot+=lw;

         add(u,v,w-lw,w);add(v,u,,);

         add(,v,lw,lw);add(v,,,lw);

         add(u,n+,lw,lw);add(n+,u,,);

     }

     int ans=;

     while(bfs()){

         for(int i=;i<=n+;i++) cur[i]=head[i];

         ans+=dfs(s,);

     }

     if(ans==tot) {

         printf("YES\n");

         for(int i=;i<m*;i+=) {printf("%d\n",e[i].f-e[i].w);}

         return ;

     }

     printf("NO\n");

 }

巴特西

[loj#115] 无源汇有上下界可行流网络流

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

题目描述

输入格式

输出格式

样例

样例输入 1

样例输出 1

样例输入 2

样例输出 2

数据范围与提示

最新文章

热门文章

巴特西

[loj#115] 无源汇有上下界可行流 网络流

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

题目描述

输入格式

输出格式

样例

样例输入 1

样例输出 1

样例输入 2

样例输出 2

数据范围与提示

最新文章

热门文章

[loj#115] 无源汇有上下界可行流网络流