上下界限制的网络流

分类: IT文章 • 2022-09-01 22:40:02

无源汇有上下界限制的网络流

题意：给n个点，及m根pipe，每根pipe用来流躺液体的，单向的，每时每刻每根pipe流进来的物质要等于流出去的物质，要使得m条pipe组成一个循环体，里面流躺物质。并且满足每根pipe一定的流量限制，范围为[Li,Ri].即要满足每时刻流进来的不能超过Ri，同时最小不能低于Li。如果可以输出yes，并且输出每条管道的流量。否则输出no。

代码：

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
  4 #define LL long long
  5 #define ULL unsigned LL
  6 #define fi first
  7 #define se second
  8 #define pb push_back
  9 #define lson l,m,rt<<1
 10 #define rson m+1,r,rt<<1|1
 11 #define max3(a,b,c) max(a,max(b,c))
 12 #define min3(a,b,c) min(a,min(b,c))
 13 #define _S(X) cout << x << ' ';
 14 #define __S(x) cout << x << endl;
 15 typedef pair<int,int> pll;
 16 const int INF = 0x3f3f3f3f;
 17 const LL mod =  (int)1e9+7;
 18 const int N = 20100;
 19 const int _M = 500100;
 20 int head[N];
 21 int M[N];
 22 int w[_M], to[_M], nx[_M], id[_M];
 23 int B[_M];
 24 int n, m, _u, _v, _w;
 25 int tot, s, t, ss, tt;
 26 int deep[N], cur[N];
 27 void add(int u, int v, int val){
 28     w[tot]  = val;
 29     to[tot] = v;
 30     nx[tot] = head[u];
 31     head[u] = tot++;
 32 }
 33 
 34 void init(){
 35     memset(head, -1, sizeof(int)*(n+3));
 36     memset(M, 0, sizeof(int)*(n+3));
 37     tot = 0;
 38     s = 1;
 39     t = n;
 40     ss = n + 1;
 41     tt = n + 2;
 42 }
 43 
 44 int bfs(int s, int t){
 45     queue<int> q;
 46     memset(deep, 0, sizeof(int)*(n+3));
 47     q.push(s);
 48     deep[s] = 1;
 49     while(!q.empty()){
 50         int u = q.front();
 51         q.pop();
 52         for(int i = head[u]; ~i; i = nx[i]){
 53             if(w[i] > 0 && deep[to[i]] == 0){
 54                 deep[to[i]] = deep[u] + 1;
 55                 q.push(to[i]);
 56             }
 57         }
 58     }
 59     if(deep[t] > 0) return 1;
 60     return 0;
 61 }
 62 int Dfs(int u, int t, int flow){
 63     if(u == t) return flow;
 64     for(int &i = cur[u]; ~i; i = nx[i]){
 65         if(deep[u]+1 == deep[to[i]] && w[i] > 0){
 66             int di = Dfs(to[i], t, min(w[i], flow));
 67             if(di > 0){
 68                 w[i] -= di, w[i^1] += di;
 69                 return di;
 70             }
 71         }
 72     }
 73     return 0;
 74 }
 75 int Dinic(int s, int t){
 76     int ans = 0, tmp;
 77     while(bfs(s, t)){
 78         for(int i = 1; i <= n+2; i++) cur[i] = head[i];
 79         while(tmp = Dfs(s, t, INF)) ans += tmp;
 80     }
 81     return ans;
 82 }
 83 int main(){
 84     while(~scanf("%d%d", &n, &m)){
 85         init();
 86         int b, c;
 87         for(int i = 1; i <= m; i++){
 88             scanf("%d%d%d%d", &_u, &_v, &b, &c);
 89             id[i] = tot; B[i] = b;
 90             add(_u,_v,c-b); add(_v,_u,0);
 91             M[_u] -= b; M[_v] += b;
 92         }
 93         int sum = 0;
 94         for(int i = 1; i <= n; i++){
 95             if(M[i] > 0) add(ss, i, M[i]), add(i, ss, 0), sum += M[i];
 96             if(M[i] < 0) add(i, tt, -M[i]), add(tt, i, 0);
 97         }
 98         int ans = Dinic(ss, tt);
 99         if(ans == sum){
100             puts("YES");
101             for(int i = 1; i <= m; i++)
102                 printf("%d
",w[id[i]^1] + B[i]);
103         }
104         else puts("NO");
105     }
106     return 0;
107 }

View Code

有源汇有上下界最大流

loj # 116

代码：

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
  4 #define LL long long
  5 #define ULL unsigned LL
  6 #define fi first
  7 #define se second
  8 #define pb push_back
  9 #define lson l,m,rt<<1
 10 #define rson m+1,r,rt<<1|1
 11 #define max3(a,b,c) max(a,max(b,c))
 12 #define min3(a,b,c) min(a,min(b,c))
 13 #define _S(X) cout << x << ' ';
 14 #define __S(x) cout << x << endl;
 15 typedef pair<int,int> pll;
 16 const int INF = 0x3f3f3f3f;
 17 const LL mod =  (int)1e9+7;
 18 const int N = 1000;
 19 const int _M = 50010;
 20 int head[N];
 21 int M[N];
 22 int w[_M], to[_M], nx[_M];
 23 int n, m, _u, _v, _w;
 24 int tot, s, t, ss, tt;
 25 int deep[N], cur[N];
 26 void add(int u, int v, int val){
 27     w[tot]  = val;
 28     to[tot] = v;
 29     nx[tot] = head[u];
 30     head[u] = tot++;
 31 }
 32 
 33 void init(){
 34     memset(head, -1, sizeof(int)*(n+3));
 35     memset(M, 0, sizeof(int)*(n+3));
 36     tot = 0;
 37     ss = n + 1;
 38     tt = n + 2;
 39 }
 40 
 41 int bfs(int s, int t){
 42     queue<int> q;
 43     memset(deep, 0, sizeof(int)*(n+3));
 44     q.push(s);
 45     deep[s] = 1;
 46     while(!q.empty()){
 47         int u = q.front();
 48         q.pop();
 49         for(int i = head[u]; ~i; i = nx[i]){
 50             if(w[i] > 0 && deep[to[i]] == 0){
 51                 deep[to[i]] = deep[u] + 1;
 52                 q.push(to[i]);
 53             }
 54         }
 55     }
 56     if(deep[t] > 0) return 1;
 57     return 0;
 58 }
 59 int Dfs(int u, int t, int flow){
 60     if(u == t) return flow;
 61     for(int &i = cur[u]; ~i; i = nx[i]){
 62         if(deep[u]+1 == deep[to[i]] && w[i] > 0){
 63             int di = Dfs(to[i], t, min(w[i], flow));
 64             if(di > 0){
 65                 w[i] -= di, w[i^1] += di;
 66                 return di;
 67             }
 68         }
 69     }
 70     return 0;
 71 }
 72 int Dinic(int s, int t){
 73     int ans = 0, tmp;
 74     while(bfs(s,t)){
 75         for(int i = 1; i <= n+2; i++) cur[i] = head[i];
 76         while(tmp = Dfs(s, t, INF)) ans += tmp;
 77     }
 78     return ans;
 79 }
 80 int main(){
 81     while(~scanf("%d%d", &n, &m)){
 82         init();
 83         scanf("%d%d", &s, &t);
 84         int b, c;
 85         for(int i = 1; i <= m; i++){
 86             scanf("%d%d%d%d", &_u, &_v, &b, &c);
 87             add(_u,_v,c-b); add(_v,_u,0);
 88             M[_u] -= b; M[_v] += b;
 89         }
 90         int sum = 0;
 91         for(int i = 1; i <= n; i++){
 92             if(M[i] > 0) add(ss, i, M[i]), add(i, ss, 0), sum += M[i];
 93             if(M[i] < 0) add(i, tt, -M[i]), add(tt, i, 0);
 94         }
 95         add(t,s,INF);
 96         add(s,t,0);
 97         int ans = Dinic(ss, tt);
 98         if(ans == sum){
 99             ans = w[--tot];
100             w[tot] = 0; w[--tot] = 0;
101             ans += Dinic(s, t);
102             printf("%d
", ans);
103         }
104         else puts("please go home to sleep");
105     }
106     return 0;
107 }

View Code

有源汇有上下界最小流

loj # 107

代码：

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
  4 #define LL long long
  5 #define ULL unsigned LL
  6 #define fi first
  7 #define se second
  8 #define pb push_back
  9 #define lson l,m,rt<<1
 10 #define rson m+1,r,rt<<1|1
 11 #define max3(a,b,c) max(a,max(b,c))
 12 #define min3(a,b,c) min(a,min(b,c))
 13 #define _S(X) cout << x << ' ';
 14 #define __S(x) cout << x << endl;
 15 typedef pair<int,int> pll;
 16 const int INF = 0x3f3f3f3f;
 17 const LL mod =  (int)1e9+7;
 18 const int N = 50100;
 19 const int _M = 350010;
 20 int head[N];
 21 int M[N];
 22 int w[_M], to[_M], nx[_M];
 23 int n, m, _u, _v, _w;
 24 int tot, s, t, ss, tt;
 25 int deep[N], cur[N];
 26 void add(int u, int v, int val){
 27     w[tot]  = val;
 28     to[tot] = v;
 29     nx[tot] = head[u];
 30     head[u] = tot++;
 31 }
 32 
 33 void init(){
 34     memset(head, -1, sizeof(int)*(n+3));
 35     memset(M, 0, sizeof(int)*(n+3));
 36     tot = 0;
 37     ss = n + 1;
 38     tt = n + 2;
 39 }
 40 
 41 int bfs(int s, int t){
 42     queue<int> q;
 43     memset(deep, 0, sizeof(int)*(n+3));
 44     q.push(s);
 45     deep[s] = 1;
 46     
 47     while(!q.empty()){
 48         int u = q.front();
 49         q.pop();
 50         for(int i = head[u]; ~i; i = nx[i]){
 51             if(w[i] > 0 && deep[to[i]] == 0){
 52                 deep[to[i]] = deep[u] + 1;
 53                 q.push(to[i]);
 54             }
 55         }
 56     }
 57     if(deep[t] > 0) return 1;
 58     return 0;
 59 }
 60 int Dfs(int u, int t, int flow){
 61     if(u == t) return flow;
 62     for(int &i = cur[u]; ~i; i = nx[i]){
 63         if(deep[u]+1 == deep[to[i]] && w[i] > 0){
 64             int di = Dfs(to[i], t, min(w[i], flow));
 65             if(di > 0){
 66                 w[i] -= di, w[i^1] += di;
 67                 return di;
 68             }
 69         }
 70     }
 71     return 0;
 72 }
 73 int Dinic(int s, int t){
 74     int ans = 0, tmp;
 75     while(bfs(s,t)){
 76         for(int i = 1; i <= n+2; i++) cur[i] = head[i];
 77         while(tmp = Dfs(s, t, INF)) ans += tmp;
 78     }
 79     return ans;
 80 }
 81 int main(){
 82     while(~scanf("%d%d", &n, &m)){
 83         init();
 84         scanf("%d%d", &s, &t);
 85         int b, c;
 86         for(int i = 1; i <= m; i++){
 87             scanf("%d%d%d%d", &_u, &_v, &b, &c);
 88             add(_u,_v,c-b); add(_v,_u,0);
 89             M[_u] -= b; M[_v] += b;
 90         }
 91         int sum = 0;
 92         for(int i = 1; i <= n; i++){
 93             if(M[i] > 0) add(ss, i, M[i]), add(i, ss, 0), sum += M[i];
 94             if(M[i] < 0) add(i, tt, -M[i]), add(tt, i, 0);
 95         }
 96         add(t,s,INF);
 97         add(s,t,0);
 98         int ans = Dinic(ss, tt);
 99         if(ans == sum){
100             ans = w[--tot];
101             w[tot] = 0; w[--tot] = 0;
102             ans -= Dinic(t, s);
103             printf("%d
", ans);
104         }
105         else puts("please go home to sleep");
106     }
107     return 0;
108 }

View Code

上下界限制的网络流

相关推荐