題意：
? ? ? 要求構造一個矩陣，給你行和，列和，還有一些點的上下范圍，輸出一個滿足題意的矩陣。

思路：
? ? ? 這個題目很經典，這是自己看上下流后接觸的第一道題，感覺很基礎的一道題目，現在我們來分析下，如果這個題目是只給行和，列和，讓我們構造矩陣應該很簡單了，直接一遍最大流，然后判斷是否滿流，滿流就把殘余網絡拿出來，整理下就是答案了，關鍵這個題

目就是不但要求滿流，某些點還有上限制，或者下限制，那么就直接是上下流唄，對了還有一個地方提醒一下，在建圖之前判斷一下有沒有輸入數據沖突的情況，下面說關鍵部分，也就是建圖，建圖之前定義幾個變量，s(源點),t（匯點）,ss（超級源點）,tt（超級匯點）.

s連接所有的行i ? ? ? ? ? ? ?add(s ,i ,行和 , 行和);
所有的列j連接終點t ? ? ? ? ?add(j ,t ,列和 ，列和);
建立一條t -> s ? ? ? ? ? ? ?add(t ,s ,0 ,INF);//為了把有源匯的最大流變成無源的
對于任意兩點i,j ? ? ? ? ? ? add(i ,j ,下限 ，上限);

簡單說下上下界網絡流可行流判斷
首先，可行流的判斷就是根據在流里面，任意點的流入和流出永遠都必須是相等的。
對于一個加邊操作，a -> b ,下界 上界 可以這樣處理
a -> b 流量為上界減去下界 ? 這個可以叫自由邊（就是不是必須流的邊）
a -> tt ,ss -> b 流量都是下界 ? 這兩個叫做必須邊，要想有解，必須邊最后必須滿流?
如果是有源的，那么我們就 add(t ,s ,0 ,INF);變成無源

最后跑一遍 ss,tt的最大流，如果滿流則有可行解，輸出答案的話知道把所有自由邊拿出來，加上下限就可以了。（因為此時下限已滿流）.

#include<stdio.h> #include<string.h> #include<queue>#define N_node 240 #define N_edge 50000 #define INF 1000000000using namespace std;typedef struct {int from ,to ,next ,cost; }STAR;typedef struct {int x ,t; }DEP;STAR E[N_edge]; DEP xin ,tou; int list[N_node] ,listt[N_node] ,tot; int deep[N_node] ,sum_must; int map[220][22][3]; int Ans[220][22];int maxx(int x ,int y) {return x > y ? x : y; }int minn(int x ,int y) {return x < y ? x : y; }void add(int a ,int b ,int c) {E[++tot].from = a;E[tot].to = b;E[tot].cost = c;E[tot].next = list[a];list[a] = tot;E[++tot].from = b;E[tot].to = a;E[tot].cost = 0;E[tot].next = list[b];list[b] = tot; }void ADD(int a ,int b ,int c ,int d ,int ss ,int tt) {add(a ,b ,d - c);add(a ,tt ,c);add(ss ,b ,c);sum_must += c; }bool BFS_Deep(int s ,int t ,int n) {xin.x = s ,xin.t = 0;queue<DEP>q;q.push(xin);memset(deep ,255 ,sizeof(deep));deep[s] = 0;while(!q.empty()){tou = q.front();q.pop();for(int k = list[tou.x] ;k ;k = E[k].next){xin.x = E[k].to;xin.t = tou.t + 1;if(deep[xin.x] != -1 || !E[k].cost)continue;deep[xin.x] = xin.t;q.push(xin);}}for(int i = 0 ;i <= n ;i ++)listt[i] = list[i];return deep[t] != -1; }int DFS_Flow(int s ,int t ,int flow) {if(s == t) return flow;int nowflow = 0;for(int k = listt[s] ;k ;k = E[k].next){listt[s] = k;int to = E[k].to;int c = E[k].cost;if(deep[to] != deep[s] + 1 || !c)continue;int tmp = DFS_Flow(to ,t ,minn(c ,flow - nowflow));nowflow += tmp;E[k].cost -= tmp;E[k^1].cost += tmp;if(nowflow == flow) break;}if(!nowflow) deep[s] = 0;return nowflow; }int DINIC(int s ,int t ,int n) {int ans = 0;while(BFS_Deep(s ,t ,n)){ans += DFS_Flow(s ,t ,INF);}return ans; }bool jude(int n ,int m) {for(int i = 1 ;i <= n ;i ++)for(int j = 1 ;j <= m ;j ++)if(map[i][j][1] > map[i][j][2]) return 0;return 1; }int main () {int a ,b ,c ,i ,j ,n ,m ,w ,T;char str[4];scanf("%d" ,&T);while(T--){scanf("%d %d" ,&n ,&m);memset(list ,0 ,sizeof(list)) ,tot = 1;sum_must = 0;int s = 0 ,t = n + m + 1 ,ss = n + m + 2 ,tt = n + m + 3;for(i = 1 ;i <= n ;i ++){scanf("%d" ,&a);ADD(s ,i ,a ,a ,ss ,tt);}for(i = 1 ;i <= m ;i ++){scanf("%d" ,&a);ADD(i + n ,t ,a ,a ,ss ,tt);}for(i = 1 ;i <= n ;i ++)for(j = 1 ;j <= m ;j ++)map[i][j][1] = 0 ,map[i][j][2] = INF;scanf("%d" ,&w);while(w--){scanf("%d %d %s %d" ,&a ,&b ,str ,&c);if(a && b){if(str[0] == '<') map[a][b][2] = minn(map[a][b][2] ,c - 1);if(str[0] == '=') map[a][b][1] = maxx(map[a][b][1] ,c) ,map[a][b][2] = minn(map[a][b][2] ,c);if(str[0] == '>') map[a][b][1] = maxx(map[a][b][1] ,c + 1);}if(a && !b){for(j = 1 ;j <= m ;j ++){if(str[0] == '<') map[a][j][2] = minn(map[a][j][2] ,c - 1);if(str[0] == '=') map[a][j][1] = maxx(map[a][j][1] ,c) ,map[a][j][2] = minn(map[a][j][2] ,c);if(str[0] == '>') map[a][j][1] = maxx(map[a][j][1] ,c + 1);}}if(!a && b){for(j = 1 ;j <= n ;j ++){if(str[0] == '<') map[j][b][2] = minn(map[j][b][2] ,c - 1);if(str[0] == '=') map[j][b][1] = maxx(map[j][b][1] ,c) ,map[j][b][2] = minn(map[j][b][2] ,c);if(str[0] == '>') map[j][b][1] = maxx(map[j][b][1] ,c + 1);}}if(!a && !b){for(i = 1 ;i <= n ;i ++)for(j = 1 ;j <= m ;j ++){if(str[0] == '<') map[i][j][2] = minn(map[i][j][2] ,c - 1);if(str[0] == '=') map[i][j][1] = maxx(map[i][j][1] ,c) ,map[i][j][2] = minn(map[i][j][2] ,c);if(str[0] == '>') map[i][j][1] = maxx(map[i][j][1] ,c + 1);}}}if(!jude(n ,m)){puts("IMPOSSIBLE");continue;}for(i = 1 ;i <= n ;i ++)for(j = 1 ;j <= m ;j ++)ADD(i ,j + n ,map[i][j][1] ,map[i][j][2] ,ss ,tt);ADD(t ,s ,0 ,INF ,ss ,tt);int Flow = DINIC(ss ,tt ,tt);if(Flow != sum_must){puts("IMPOSSIBLE");continue;}for(i = 2 ;i <= tot ;i ++)if(E[i].from >= 1 && E[i].from <= n && E[i].to >= n + 1 && E[i].to <= n + m)Ans[E[i].from][E[i].to - n] = E[i^1].cost + map[E[i].from][E[i].to - n][1];for(i = 1 ;i <= n ;i ++)for(j = 1 ;j <= m ;j ++)if(j == m)printf("%d\n" ,Ans[i][j]);else printf("%d " ,Ans[i][j]);if(T) puts("");}return 0; }

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的POJ 2396 构造矩阵（上下流）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。