sicily 1303 最大权 km

//这种题编过就变水了 #include <iostream> #include <cstring> #include <cstdio> #define Mx 101; using namespace std; int n,result,d; int w[101][101],kmx[101],kmy[101]; bool _usex[101],_usey[101]; int linky[101]; bool find( int i ) { _usex[i] = true; for( int j = 1;j <= n;j++ ) { if( _usey[j] ) continue; int t = kmx[i] + kmy[j] - w[i][j]; if( t == 0 ) { _usey[j] = true; if( !linky[j] || find( linky[j] ) ) { linky[j] = i; return true; } } else if( d > t ) d = t; } return false; } void KM() { for( int i = 1;i <= n;i++ ) { for( ; ; ) { memset( _usex,false,sizeof(_usex) ); memset( _usey,false,sizeof(_usey) ); d = Mx; if( find( i ) ) break; for( int j = 1;j <= n;j++ ) { if( _usex[j] ) kmx[j] -= d; if( _usey[j] ) kmy[j] += d; } } } } int main() { //freopen( "1.txt","r",stdin ); while( scanf("%d",&n) && 0 != n ) { result = 0; memset( linky,0,sizeof( linky ) ); memset( kmx,0,sizeof( kmx ) ); memset( kmy,0,sizeof( kmy ) ); for( int i = 1;i <= n;i++ ) for( int j = 1;j <= n;j++ ) { scanf( "%d",&w[i][j] ); if( kmx[i] < w[i][j] ) kmx[i] = w[i][j]; } KM(); for( int i = 1;i <= n;i++ ) result += ( kmx[i] + kmy[i] ); printf( "%d/n",result ); } return 0; }