HDU 5513 효율 트 리 생 성 트 리 계수+상태 압축
7401 단어 생 성 트 리 개수
， http://acm.hdu.edu.cn/showproblem.php?pid=5513 ， ， n*m，n<800, m<8， ， 。 ， ， ， 1+（ +1， +1）， ， ， 。。。 ，g[0/1][st] ，st m ，st ， m ， 8 （m<8）， i， i-1 i-m ， ， ， i-m ， NOI2007 http://www.lydsy.com/JudgeOnline/problem.php?id=1494 Tree ， ， http://blog.csdn.net/whjpji/article/details/7617796
#include
#include
#include
#include
typedef __int64 ll;
using namespace std;
const int mod = 1e9+7;
int left[805][10], up[805][10], v[1005], a[8], b[8];
ll f[2][1005], g[2][1005];
int n, m, cnt, qe = 0;;
const ll maxn = 4294967295;
int nxt[4][1005];
int find( int sta )
{
int l, r, mid, pos = -1;
l = 1, r = cnt-1;
while( l <= r ){
mid = (l+r)>>1;
if( v[mid] == sta ){
pos = mid;
break;
}
if( v[mid] > sta ) r = mid-1;
else l = mid+1;
}
return pos;
}//
void dfs( int x, int y, int maxn )
{
int sta, i, j;
if( x > y ){
sta = a[1];
for( i = 2; i <= m; i ++ ){
sta = sta << 3;
sta = sta|a[i];
}
v[cnt++] = sta;
return;
}
for( a[x] = 1; a[x] <= maxn; a[x] ++ ){
if( a[x] == maxn )dfs( x+1, m, maxn+1 );
else dfs( x+1, m, maxn );
}
}//
int modify( int x, int id )
{
int b[10], i, j, k, r[10], ans = 0;
int vis[10];
memset( vis, 0, sizeof(vis) );
k = x;
for( i = m; i > 0 ; i -- ){
b[i] = k & 7;
if( id == 1 && b[i] == 1 ){
b[i] = a[m];
}
k >>= 3;
}
for( i = 1, j = 1; i <= m; i ++ ){
if( vis[b[i]] == 0 ){
r[i] = j;
vis[b[i]] = j;
j ++;
}
else{
r[i] = vis[b[i]];
}
}
ans = r[1];
for( i = 2; i <= m; i ++ ){
ans <<= 3;
ans = ans | r[i];
}
return ans;
}//
void intit()
{
int i, j;
scanf("%d %d", &n, &m);
for( int i = 1; i <= n; i ++ )
for( int j = 2; j <= m; j ++ )
scanf("%d", &left[i][j]);
for( int i = 2; i <= n; i ++ )
for( int j = 1; j <= m; j ++ )
scanf("%d", &up[i][j]);
cnt = 1;
memset( a, 0, sizeof(a) );
dfs( 1, m, 1 );
sort( v+1, v+cnt );
for( i = 1; i < cnt; i ++ ){
int st = v[i], nk, pos;
for( int l = m, tmp = st; l >= 1; l -- ){
a[l] = tmp & 7;
tmp >>= 3;
}
nk = modify( ( (st << 3) | a[m] ) & ( ( 1 << (3*m) ) - 1 ), 1 );
pos = find(nk);
nxt[0][i] = pos;
nk = modify( ( (st << 3) | a[m] ) & ( ( 1 << (3*m) ) - 1 ), -1 );
pos = find(nk);
nxt[1][i] = pos;
nk = modify( ( (st << 3) | 1 ) & ( ( 1 << (3*m) ) - 1 ), -1 );
pos = find(nk);
nxt[2][i] = pos;
nk = modify( ( (st << 3) | 0 ) & ( ( 1 << (3*m) ) - 1 ), -1 );
pos = find(nk);
nxt[3][i] = pos;
}//
}
void solve()
{
int now = 0, bef = 1, i, j, ok, p, q;
memset( g, 0, sizeof(g) );
for( int k = 0; k < 1000; k ++ )f[now][k] = f[bef][k] = maxn;
f[now][1] = 0; g[now][1] = 1;
for( i = 1; i <= n; i ++ )
for( j = 1; j <= m; j ++ ){
if( i == 1 && j == 1 )continue;
swap( now, bef );
memset( g[now], 0, sizeof(g[now]) );
for( int k = 0; k < 1000; k ++ )f[now][k] = maxn;
for( p = 1; p < cnt; p ++ ){
int st = v[p];
if( f[bef][p] == maxn )continue;
ok = 0;
for( int l = 1, tmp = st; l < m; l ++ ){
if( (tmp & 7) == 1 ){
ok = 1;
}
tmp >>= 3;
}
for( int l = m, tmp = st; l >= 1; l -- ){
a[l] = tmp & 7;
tmp >>= 3;
}
if( i > 1 && j > 1 && a[1] != a[m] ){//
int tmp = f[bef][p]+left[i][j]+up[i][j];
int cu = nxt[0][p];
if( tmp == f[now][cu] ){
g[now][cu] = ( g[now][cu] + g[bef][p] * 3 ) % mod;
}
else if( tmp < f[now][cu] ){
f[now][cu] = tmp;
g[now][cu] = g[bef][p]*3%mod;
}
}
if( j > 1 && ok ){
int tmp = f[bef][p]+left[i][j];
int cu = nxt[1][p];
if( tmp == f[now][cu] ){
g[now][cu] = ( g[now][cu] + g[bef][p] * 2 ) % mod;
}
else if( tmp < f[now][cu] ){
f[now][cu] = tmp;
g[now][cu] = g[bef][p]*2%mod;
}
}
if( i > 1 ){
int tmp = f[bef][p]+up[i][j];
int cu = nxt[2][p];
if( tmp == f[now][cu] ){
g[now][cu] = ( g[now][cu] + g[bef][p] * 2 ) % mod;
}
else if( tmp < f[now][cu] ){
f[now][cu] = tmp;
g[now][cu] = g[bef][p]*2%mod;
}
}
if( ok ){
int tmp = f[bef][p];
int cu = nxt[3][p];
if( tmp == f[now][cu] ){
g[now][cu] = ( g[now][cu] + g[bef][p] ) % mod;
}
else if( tmp < f[now][cu] ){
f[now][cu] = tmp;
g[now][cu] = g[bef][p]%mod;
}
}//
}
// for( int k = 1; k < cnt; k ++ ){
// printf("%d %d %d %I64d %I64d
", i, j, k, f[now][k], g[now][k]);
// }
}
printf("Case #%d: %I64d %I64d
", ++qe, f[now][1], g[now][1] );
}
int main()
{
int T;
//freopen("out.txt", "w", stdout);
scanf("%d", &T);
while( T -- ){
intit();
solve();
}
}
좋은 웹페이지 즐겨찾기
