AndyZh说过:
“我们想求一堆人的排列总数,它等于在这一堆人中 减去 每一个 入度为 0 的人,剩下的人的排列总数的和。具体实现也借助了回溯法。
如果只剩下一个人,那么排列总数为1,这是递归的边界。 ”
#include <cstdio>
#include <string>
#include <map>
using namespace std;
int M, N, a[16][16];
char name[16][100];
double val[65536]; // 位操作
int power[16]; // 求每一位是否存在
int in[16]; // 入度
int init ()
...{
if ( scanf ( "%d", &N ) == EOF )
return 0;
int i, j;
char x[100], y[100];
memset ( a, 0, sizeof ( a ) );
M = 0;
for ( i = 0; i < N; i ++ )
...{
scanf ( "%s%s", x, y );
int u = -1, v = -1;
for ( j = 0; j < M; j ++ )
...{
if ( !strcmp ( name[j], x ) )
u = j;
if ( !strcmp ( name[j], y ) )
v = j;
}
if ( u == -1 )
...{
strcpy ( name[M], x );
u = M ++;
}
if ( v == -1 )
...{
strcpy ( name[M], y );
v = M ++;
}
if ( u != v )
a[u][v] = 1;
}
memset ( in, 0x00, sizeof ( in ) );
for ( i = 0; i < M; i ++ )
for ( j = 0; j < M; j ++ )
...{
if ( a[i][j] )
in[j] ++;
}
return N;
}
double getValue ( int x )
...{
if ( val[x] >= 0 )
return val[x];
int i, j;
val[x] = 0;
for ( i = 0; i < M; i ++ )
...{
// 当入度为0时可以提取在队列最前方
if ( !in[i] && ( ( x & power[i] ) == power[i] ) )
...{
for ( j = 0; j < M; j ++ )
...{
if ( a[i][j] )
in[j] --;
}
val[x] += getValue ( x ^ power[i] );
for ( j = 0; j < M; j ++ )
...{
if ( a[i][j] )
in[j] ++;
}
}
}
return val[x];
}
void dp ()
...{
memset ( val, 0xff, sizeof ( val ) );
int i;
for ( i = 0; i < M; i ++ )
power[i] = 1 << i;
for ( i = 0; i < M; i ++ )
val[power[i]] = 1;
int x = ( 1 << M ) - 1;
val[x] = getValue ( x );
printf ( "%.0f ", val[x] );
//pt ();
}
int main ()
...{
//freopen ( "in.txt", "r", stdin );
//freopen ( "out.txt", "w", stdout );
while ( init () )
...{
dp ();
}
return 0;
}
#include <string>
#include <map>
using namespace std;
int M, N, a[16][16];
char name[16][100];
double val[65536]; // 位操作
int power[16]; // 求每一位是否存在
int in[16]; // 入度
int init ()
...{
if ( scanf ( "%d", &N ) == EOF )
return 0;
int i, j;
char x[100], y[100];
memset ( a, 0, sizeof ( a ) );
M = 0;
for ( i = 0; i < N; i ++ )
...{
scanf ( "%s%s", x, y );
int u = -1, v = -1;
for ( j = 0; j < M; j ++ )
...{
if ( !strcmp ( name[j], x ) )
u = j;
if ( !strcmp ( name[j], y ) )
v = j;
}
if ( u == -1 )
...{
strcpy ( name[M], x );
u = M ++;
}
if ( v == -1 )
...{
strcpy ( name[M], y );
v = M ++;
}
if ( u != v )
a[u][v] = 1;
}
memset ( in, 0x00, sizeof ( in ) );
for ( i = 0; i < M; i ++ )
for ( j = 0; j < M; j ++ )
...{
if ( a[i][j] )
in[j] ++;
}
return N;
}
double getValue ( int x )
...{
if ( val[x] >= 0 )
return val[x];
int i, j;
val[x] = 0;
for ( i = 0; i < M; i ++ )
...{
// 当入度为0时可以提取在队列最前方
if ( !in[i] && ( ( x & power[i] ) == power[i] ) )
...{
for ( j = 0; j < M; j ++ )
...{
if ( a[i][j] )
in[j] --;
}
val[x] += getValue ( x ^ power[i] );
for ( j = 0; j < M; j ++ )
...{
if ( a[i][j] )
in[j] ++;
}
}
}
return val[x];
}
void dp ()
...{
memset ( val, 0xff, sizeof ( val ) );
int i;
for ( i = 0; i < M; i ++ )
power[i] = 1 << i;
for ( i = 0; i < M; i ++ )
val[power[i]] = 1;
int x = ( 1 << M ) - 1;
val[x] = getValue ( x );
printf ( "%.0f ", val[x] );
//pt ();
}
int main ()
...{
//freopen ( "in.txt", "r", stdin );
//freopen ( "out.txt", "w", stdout );
while ( init () )
...{
dp ();
}
return 0;
}