本文主要是介绍【HDU】4975 A simple Gaussian elimination problem. 网络流——行列建边，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：【HDU】4975 A simple Gaussian elimination problem.
题目分析：这题和某一场的多校的题目出奇的像啊！重要的是我一开始还以为不可能会出一样的题。。结果迟迟没写啊。。。后来觉得实在想不出什么对策了，虽然觉得给的是0~9很特殊，但是利用不起来，果断还是敲了网络流了。。首先建图很简单，源点向行建边，容量为行和，列向汇点建边，容量为列和，然后所有的行向所有的列建边，跑一边最大流，如果流量和元素总和不相等则无解。
现在关键就是求单解还是多解了。姿势不对可是就会TLE的哦~~
然后我很光荣的TLE了 T U T。。。
首先用残余网络判环的方法可以过（难以置信。。。），然后我用O(n^3)寻找可以使得多解存在的四个点的矩阵（矩阵的四个点如果满足其中一条对角线上的两点可以变小，另一条上的两个可以变大，则说明存在多解），不出意外的TLE了！不过我郁闷了很久突然想到如果一行的元素都为0或者都为9时这一行一定是无用的（不可能同时存在两点一点可以增大，另一点可以减小），将其判掉，然后再交了一发，期待的看着板板，然后终于给我返回了一个期待已久的———TLE！
郁闷至极啊！！！
然后想了想就弃疗了再特判掉列吧，怀着不可能AC的心再交了一发。。。然后在我不可思议的眼中，它竟然AC了？！
果然流氓剪枝很强啊。。。
虽然还是跑不过前面大神的代码，但是已经满足啦~~
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <math.h>
using namespace std ;#define REP( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define CLR( a , x ) memset ( a , x , sizeof a )
#define CPY( a , x ) memcpy ( a , x , sizeof a )const int MAXN = 1005 ;
const int MAXE = 2000000 ;
const int INF = 0x3f3f3f3f ;struct Edge {int v , c , n ;Edge () {}Edge ( int v , int c , int n ) : v ( v ) , c ( c ) , n ( n ) {}
} ;struct ISAP {Edge E[MAXE] ;int H[MAXN] , cntE ;int d[MAXN] , cur[MAXN] , num[MAXN] , pre[MAXN] ;int Q[MAXN] , head , tail ;int s , t , nv ;int flow ;void init () {cntE = 0 ;CLR ( H , -1 ) ;}void addedge ( int u , int v , int c ) {E[cntE] = Edge ( v , c , H[u] ) ;H[u] = cntE ++ ;E[cntE] = Edge ( u , 0 , H[v] ) ;H[v] = cntE ++ ;}void rev_bfs () {CLR ( d , -1 ) ;CLR ( num , 0 ) ;head = tail = 0 ;d[t] = 0 ;num[d[t]] = 1 ;Q[tail ++] = t ;while ( head != tail ) {int u = Q[head ++] ;for ( int i = H[u] ; ~i ; i = E[i].n ) {int v = E[i].v ;if ( ~d[v] ) continue ;d[v] = d[u] + 1 ;Q[tail ++] = v ;num[d[v]] ++ ;}}}int isap () {rev_bfs () ;CPY ( cur , H ) ;flow = 0 ;int u = pre[s] = s , i , pos , minv ;while ( d[s] < nv ) {if ( u == t ) {int f = INF ;for ( i = s ; i != t ; i = E[cur[i]].v )if ( f > E[cur[i]].c ) {f = E[cur[i]].c ;pos = i ;}for ( i = s ; i != t ; i = E[cur[i]].v ) {E[cur[i]].c -= f ;E[cur[i] ^ 1].c += f ;}flow += f ;u = pos ;}for ( i = cur[u] ; ~i ; i = E[i].n )if ( E[i].c && d[u] == d[E[i].v] + 1 ) break ;if ( ~i ) {cur[u] = i ;pre[E[i].v] = u ;u = E[i].v ;} else {if ( 0 == -- num[d[u]] ) break ;for ( minv = nv , i = H[u] ; ~i ; i = E[i].n ) {if ( E[i].c && minv > d[E[i].v] ) {minv = d[E[i].v] ;cur[u] = i ;}}d[u] = minv + 1 ;num[d[u]] ++ ;u = pre[u] ;}}return flow ;}
} S ;int n , m ;
int G[MAXN][MAXN] ;
int row[505] , col[505] ;
bool vis[505][505] ;bool unique () {CLR ( vis , 0 ) ;FOR ( i , 1 , n ) {if ( row[i] == 0 || row[i] == 9 * m ) continue ;FOR ( j , 1 , m ) {if ( col[j] == 0 || col[j] == 9 * n ) continue ;FOR ( k , j + 1 , m ) {int tmp1 = 0 , tmp2 = 0 ;if ( G[i][j] && G[i][k] != 9 ) {if ( vis[j][k] ) return 0 ;tmp1 = 1 ;}if ( G[i][k] && G[i][j] != 9 ) {if ( vis[k][j] ) return 0 ;tmp2 = 1 ;}if ( tmp1 ) vis[k][j] = 1 ;if ( tmp2 ) vis[j][k] = 1 ;}}}//FOR ( i , 1 , m ) FOR ( j , 1 , m ) printf ( "%d\n" , vis[i][j] ) ;return 1 ;
}void solve () {int sum1 = 0 , sum2 = 0 ;S.init () ;scanf ( "%d%d" , &n , &m ) ;S.s = 0 ;S.t = n + m + 1 ;S.nv = S.t + 1 ;FOR ( i , 1 , n ) {scanf ( "%d" , &row[i] ) ;S.addedge ( S.s , i , row[i] ) ;sum1 += row[i] ;}FOR ( i , 1 , m ) {scanf ( "%d" , &col[i] ) ;S.addedge ( i + n , S.t , col[i] ) ;sum2 += col[i] ;}if ( sum1 != sum2 ) {printf ( "So naive!\n" ) ;return ;}FOR ( i , 1 , n ) FOR ( j , 1 , m ) S.addedge ( i , j + n , 9 ) ;if ( sum1 != S.isap () ) {printf ( "So naive!\n" ) ;return ;}FOR ( u , 1 , n ) {for ( int i = S.H[u] ; ~i ; i = S.E[i].n ) {int v = S.E[i].v ;if ( v == 0 ) continue ;G[u][v - n] = 9 - S.E[i].c ;}}//FOR ( i , 1 , n ) FOR ( j , 1 , m ) printf ( "%d%c" , G[i][j] , j < m ? ' ' : '\n' ) ;if ( unique () ) printf ( "So simple!\n" ) ;else printf ( "So young!\n" ) ;
}int main () {int T , cas = 0 ;scanf ( "%d" , &T ) ;while ( T -- ) {printf ( "Case #%d: " , ++ cas ) ;solve () ;}return 0 ;
}这篇关于【HDU】4975 A simple Gaussian elimination problem. 网络流——行列建边的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
