HDU 4888 神奇最大流行进列出构造矩阵

题意： 给你一个N ，M 构造一个N*M的矩阵，矩阵中每个元素为0-K；

给你每行的和与每列的和。

如果解法唯一 ，输出解法

如果解法不唯一，输出一句话，

如果没有解法，输出一句话。

题解： 经典建图

s ---> 每个行节点，流量为行和

每个列节点----〉t，流量为列和

每行每列单独连接，流量为K

代码：

#include
  
   
#include
   
     #include
    
      #define INF 1000000000 #define N 1005 
     using namespace std
     ; int list
     [N
     ], listt
     [N
     ], deep
     [N
     ], tot
     , n
     , m
     , k
     , flagg
     , mark_dfs
     [N
     ]; struct Node
      { int date
     , value
     , next
     ; }cun
     [2000005
     ]; struct Edge
      { int x
     , t
     ; }old
     , xin
     ; void add
     (int a
     , int b
     , int c
     ) { cun
     [++tot
     ].date
      = b
     ; cun
     [tot
     ].value
      = c
     ; cun
     [tot
     ].next
      = list
     [a
     ]; list
     [a
     ] = tot
     ; cun
     [++tot
     ].date
      = a
     ; cun
     [tot
     ].value
      = 0
     ; cun
     [tot
     ].next
      = list
     [b
     ]; list
     [b
     ] = tot
     ; } int bfs
     (int s
     , int t
     , int n
     ) { queue
     <Edge
     > p
     ; xin
     .x
      = s
     ; xin
     .t
      = 0
     ; p
     .push
     (xin
     ); memset
     (deep
     ,255
     ,sizeof(deep
     )); deep
     [s
     ] = 0
     ; while(!p
     .empty
     ()) { old
      = p
     .front
     (); p
     .pop
     (); for(int i
      = list
     [old
     .x
     ]; i
     ; i
      = cun
     [i
     ].next
     ) { int date
      = cun
     [i
     ].date
     ; int value
      = cun
     [i
     ].value
     ; xin
     .x
      = date
     ; xin
     .t
      = old
     .t
      + 1
     ; if(value
      == 0
      || deep
     [date
     ] != -1
     ) continue; deep
     [date
     ] = xin
     .t
     ; p
     .push
     (xin
     ); } } for(int i
      = 0
     ; i
      <= n
     ; i
     ++) { listt
     [i
     ] = list
     [i
     ]; } return deep
     [t
     ] != -1
     ; } int minn
     ( int a
     , int b
     ) { if(a
      < b
     ) return a
     ; return b
     ; } int dfs
     (int s
     , int t
     , int min
     ) { if(s
      == t
     ) return min
     ; int neww
      = 0
     ; for(int i
      = listt
     [s
     ]; i
     ; i
      = cun
     [i
     ].next
     ) { listt
     [s
     ] = i
     ; int date
      = cun
     [i
     ].date
     ; int value
      = cun
     [i
     ].value
     ; if(value
      == 0
      || deep
     [date
     ] != deep
     [s
     ] + 1
     ) { continue; } int m
      = dfs
     (date
     , t
     , minn
     (value
     , min
      - neww
     )); neww
      += m
     ; cun
     [i
     ].value
      -= m
     ; cun
     [i
     ^1
     ].value
      += m
     ; if(neww
      == min
     ) break; } if(neww
      == 0
     ) deep
     [s
     ] = 0
     ; return neww
     ; } int dinic
     ( int s
     , int t
     , int n
     ) { int num
      = 0
     ; while(bfs
     (s
     , t
     , n
     )) { num
      += dfs
     (s
     , t
     , INF
     ); } return num
     ; } int dfs_1
     (int s
     , int p
     ) { for(int i
      = list
     [s
     ]; i
     ; i
      = cun
     [i
     ].next
     ) { int date
      = cun
     [i
     ].date
     ; if(i
      == (p
     ^1
     )) continue; if(cun
     [i
     ].value
     ) { if(mark_dfs
     [date
     ]) {return 1
     ;} mark_dfs
     [date
     ] = 1
     ; if(dfs_1
     (date
     , i
     )) return 1
     ; mark_dfs
     [date
     ] = 0
     ; } } return 0
     ; } void build
     () { int a
     , s
      = n
      + m
      + 10
     , t
      = s
      + 1
     , sum1
      = 0
     , sum2
      = 0
     ; memset
     (list
     ,0
     ,sizeof(list
     )); memset
     (mark_dfs
     ,0
     ,sizeof(mark_dfs
     )); tot
      = 1
     ; flagg
      = 0
     ; for(int i
      = 1
     ; i
      <= n
     ; i
     ++ ) { scanf
     ("%d"
     , &a
     ); sum1
      += a
     ; add
     (s
     , i
     , a
     ); } for(int i
      = 1
     ;i
      <= m
     ; i
     ++ ) { scanf
     ("%d"
     , &a
     ); sum2
      += a
     ; add
     (i
      + n
     , t
     , a
     ); } if(sum1
      != sum2
     ) {printf
     ("Impossible\n"
     ); return;} int kk
      = tot
     ; for(int i
      = 1
     ; i
      <= n
     ; i
     ++ ) for(int j
      = 1
     ; j
      <= m
     ; j
     ++ ) { add
     (i
     , j
      + n
     , k
     ); } int mm
      = dinic
      ( s
     , t
     , t
      + 10
      ), flag
      = 0
     ; if(mm
      != sum1
     ) {printf
     ("Impossible\n"
     ); return;} for(int i
      = 1
     ; i
      <= n
     ; i
     ++ ) { if( dfs_1
     (i
     , -1
     ) ) { flagg
      = 1
     ; break; } } kk
     ++; if(flagg
     ) printf
     ("Not Unique\n"
     ); else { printf
     ("Unique\n"
     ); for(int i
      = 1
     ; i
      <= n
     ; i
     ++) { for(int j
      = 1
     ; j
      <= m
     ; j
     ++) { if(j
      == 1
     ) printf
     ("%d"
     ,k
      - cun
     [kk
     ].value
     ); else printf
     (" %d"
     ,k
      - cun
     [kk
     ].value
     ); kk
      += 2
     ; } printf
     ("\n"
     ); } } } int main() { while(scanf
     ("%d%d%d"
     ,&n
     , &m
     , &k
     )!=EOF
     ) { build
     (); } }