一个网络,求出一个流,使得每条边的流量必须>=Li且<=Hi,每个点必须满足总流入量=总流出量(流量守恒)(这个流的特点是循环往复,无始无终).

如果有解的话输出每条边的流量

1 #include
     
        2 using namespace std;  3 typedef long long ll;  4 namespace DINIC  5 {  6     const int MAXN=500+10;  7     const int MAXM=4e5+10;  8     const int INF=0x3f3f3f3f;  9     struct Edge 10     { 11         int u,v,cap,nxt; 12         Edge(){} 13         Edge(int _u,int _v,int _cap,int _nxt):u(_u),v(_v),cap(_cap),nxt(_nxt){} 14     }E[MAXM]; 15     int head[MAXN],dis[MAXN],vis[MAXN]; 16     int tol; 17     void init() 18     { 19         tol=0; 20         memset(head,-1,sizeof(head)); 21     } 22     void addedge(int u,int v,int cap) 23     { 24         E[tol]=Edge(u,v,cap,head[u]);//正向边 25         head[u]=tol++; 26         E[tol]=Edge(v,u,0,head[v]);//反向边容量为0 27         head[v]=tol++; 28     } 29     bool BFS(int S,int T) 30     { 31         queue
      
        q; 32         q.push(S); 33         memset(dis,0x3f,sizeof(dis)); 34         dis[S]=0; 35         while(!q.empty()) 36         { 37             int x=q.front(); 38             q.pop(); 39             for(int i=head[x];~i;i=E[i].nxt) 40             { 41                 if(E[i].cap>0&&dis[E[i].v]==INF) 42                 { 43                     dis[E[i].v]=dis[x]+1; 44                     if(E[i].v==T) 45                         return true; 46                     q.push(E[i].v); 47                 } 48             } 49         } 50         return dis[T]
       
        0) 61             { 62                 int flow=dfs(E[i].v,min(maxflow,E[i].cap),T); 63                 if(flow) 64                 { 65                     ret+=flow; 66                     maxflow-=flow; 67                     E[i].cap-=flow;//正向边流量降低 68                     E[i^1].cap+=flow; //反向边流量增加 69                 } 70                 if(maxflow==0) 71                     break; 72             } 73         } 74         return ret;//找不到增广路退出 75     } 76     ll dinic(int S,int T,int N) 77     { 78         ll ans=0; 79         while(BFS(S,T))//建立分层图 80         { 81             int flow; 82             for(int i=0;i<=N;i++)//初始化vis 83             { 84                 vis[i]=head[i]; 85             } 86             while(flow=dfs(S,INF,T))//一次BFS可以进行多次增广 87                 ans+=(ll)flow; 88         } 89         return ans; 90     } 91 } 92 using namespace DINIC; 93 int a[MAXN],low[MAXM]; 94 int n,m; 95 bool judge() 96 { 97     for(int i=head[0];~i;i=E[i].nxt) 98     { 99         if(E[i].cap!=0)100             return false;101     }102     for(int i=head[n+1];~i;i=E[i].nxt)103     {104         if(E[i^1].cap!=0)105             return false;106     }107     return true;108 }109 void solve()110 {111     int cnt;112     memset(a,0,sizeof(a));113     init();114     for(int i=1;i<=m;i++)115     {116         int u,v,up;117         scanf("%d%d%d%d",&u,&v,&low[i],&up);118         a[v]+=low[i];a[u]-=low[i];119         addedge(u,v,up-low[i]);120     }121     cnt=tol;122     for(int i=1;i<=n;i++)123     {124         if(a[i]>0)125             addedge(0,i,a[i]);126         if(a[i]<0)127             addedge(i,n+1,-a[i]);128     }129     dinic(0,n+1,n+2);130     if(!judge())131     {132         puts("NO");133         return ;134     }135     puts("YES");136     for(int i=0;i