題意：
? ? ? 讓你構(gòu)造一個矩陣，滿足每一行的和，和每一列的和都等于他給的，還要判斷答案是否唯一，還有一點就是矩陣內(nèi)所有的數(shù)字都是[0,k]范圍的。

思路：

? ? ? 這個題目看完就讓我想起了hdu3338，那個題目做了好久啊！哎！對于構(gòu)造矩陣還是很簡單的，我們構(gòu)造兩個點起s點和終點e，建圖如下：

s -> 所有行 ? ? ? 流量是當(dāng)前行和

所有行 -> 所有列 ?流量為k

所有列 -> e ? ? ? 流量為當(dāng)前列和

這樣矩陣就構(gòu)造好了，如果輸出答案就直接去殘余網(wǎng)絡(luò)里面找就行了，下面說一下怎么判斷最大流是否唯一，其實這個我們可以通過殘余網(wǎng)絡(luò)來找，只要能在殘余網(wǎng)絡(luò)上找到環(huán)就行了，這個結(jié)論值存在于無環(huán)圖中，這里說的無環(huán)圖是指建圖的時候的正向圖是無環(huán)的，對于這個題目就是無環(huán)圖，這個題目還有一個坑點，就是一開始我是從終點開始搜直接找環(huán)，沒有從起點是因為起點已經(jīng)滿流，正向流量全是0，根本跑不懂，但是從終點跑各種超時，超時出翔了，無語了我又枚舉所有終點所連接的點開始跑，還是超時，最后是枚舉起點所連接的點

開始跑的，500ms AC，我有點蛋疼，理論上對于一個環(huán)而言從哪個位置跑都可以找到環(huán)，我估計是數(shù)據(jù)里面給的 "能得到唯一答案" 的數(shù)據(jù)過多，這樣就讓很多正向的流量變成0，或者是不至于走了好幾層才變成0，哎!這個不科學(xué)啊！

#include<stdio.h> #include<string.h> #include<queue>#define N_node 810 #define N_edge 350000 #define INF 1000000000 using namespace std;typedef struct {int to ,next ,cost; }STAR;typedef struct {int x ,t; }DEP;STAR E[N_edge]; DEP xin ,tou; int list[N_node] ,list1[N_node] ,tot; int deep[N_node] ,map[405][405];void add(int a ,int b ,int c) {E[++tot].to = b;E[tot].cost = c;E[tot].next = list[a];list[a] = tot;E[++tot].to = a;E[tot].cost = 0;E[tot].next = list[b];list[b] = tot; }int minn(int x ,int y) {return x < y ? x : y; }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){deep[xin.x] = xin.t;q.push(xin);}}}for(int i = 0 ;i <= n ;i ++)list1[i] = list[i];return deep[t] != -1; }int DFS(int s ,int t ,int flow) {if(s == t) return flow;int nowflow = 0;for(int k = list1[s] ;k ;k = E[k].next){list1[s] = k;int c = E[k].cost;int to = E[k].to;if(!c || deep[to] != deep[s] + 1) continue;int tmp = DFS(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(s ,t ,INF);}return ans; }int mark_r; int mark[N_node]; void DFS_R(int from ,int s) {for(int k = list[s] ;k && !mark_r ;k = E[k].next){int to = E[k].to;if(k == (from ^ 1) || !E[k].cost) continue;if(mark[to]) mark_r = 1;mark[to] = 1;if(!mark_r) DFS_R(k ,to);mark[to] = 0;} }int main () {int n ,m ,i ,j ,k ,num;int s1 ,s2;while(~scanf("%d %d %d" ,&n ,&m ,&k)){memset(list ,0 ,sizeof(list)) ,tot = 1;int mkk = 0;for(s1 = 0 ,i = 1 ;i <= n ;i ++){scanf("%d" ,&num);add(0 ,i ,num);if(k * m < num) mkk = 1;s1 += num;}for(s2 = 0 ,i = 1 ;i <= m ;i ++){scanf("%d" ,&num);add(i + n ,n + m + 1 ,num);if(k * n < num) mkk = 1;s2 += num;}if(s1 != s2 || mkk){puts("Impossible"); continue;}int mk = tot + 1;for(i = 1 ;i <= n ;i ++)for(j = 1 ;j <= m ;j ++)add(i ,j + n ,k);int sum = DINIC(0 ,n + m + 1 ,n + m + 1);if(sum != s1){puts("Impossible"); continue;}mark_r = 0;memset(mark , 0 ,sizeof(mark));mark[n+m+1] = 1;for(i = 1 ;i <= n ;i ++){DFS_R(0 ,i);if(mark_r) break;}if(mark_r){puts("Not Unique");continue;}puts("Unique");int t = 0;for(i = mk ;i <= tot ;i += 2){printf("%d" ,k - E[i].cost);if(++t % m == 0) puts("");else printf(" ");} }return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu4888 最大流（构造矩阵）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。