Problem's Link:

Mean:

n个人，m对朋友关系，每个人的朋友中又分为在线好友和不在线好友，对于每个人都要保证在线好友和不在线好友一样多，求方案数有多少种。

analyse:

我们用m对关系建立一个无向图（存边即可），同时统计每个节点的度。

首先可以确定的是：如果某个节点的度是奇数，很显然answer=0。

将每个节点的度分为两组：online和offonline。

初始时，每个节点的online和offonline是相等的。

然后就是dfs统计答案。

如何统计呢？

dfs统计答案的实质就是枚举每一条边的两种属性（online和offonline）.

如果枚举得到的状态能满足条件，在程序中可以走到m+1状态，此时是一种答案，ans++。

在dfs时，我们把每条边对应的两个节点的online值同增同减，且回溯时将减掉的online加回来，这样就保证了online和offonline在相同数量的边的情况下是相等的。

这种做法还是很巧妙的。

Time complexity: O(N)

Source code:

/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-07-24-08.09
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define  LL long long
#define  ULL unsigned long long
using
namespace
std; 
int n 
,
m
,
ans; 
int
time
[
10
],
online
[
10
],
offonline
[
10
];
struct
edge
{ 
int
u
,
v; 
}
e
[
30
];
void
DFS( 
int
x ) 
{ 
if( 
x
==
m
+
1 ) 
{ 
ans
++; 
return; 
}
int
u
=
e
[
x
].
u; 
int
v
=
e
[
x
].
v; 
if( 
online
[
u
]
&&
online
[
v
] ) 
{ 
online
[
u
]
--; 
online
[
v
]
--; 
DFS( 
x
+
1 ); 
online
[
u
]
++; 
online
[
v
]
++; 
}
if( 
offonline
[
u
]
&&
offonline
[
v
] ) 
{ 
offonline
[
u
]
--; 
offonline
[
v
]
--; 
DFS( 
x
+
1 ); 
offonline
[
u
]
++; 
offonline
[
v
]
++; 
}
return ; 
}
int
main() 
{ 
ios_base
::
sync_with_stdio( 
false ); 
cin
.
tie( 
0 ); 
int
t; 
cin
>>
t; 
while( 
t
-- ) 
{ 
ans
=
0; 
memset( 
time
,
0
,
sizeof( 
time ) ); 
memset( 
e
,
0
,
sizeof( 
e ) ); 
memset( 
online
,
0
,
sizeof( 
online ) ); 
memset( 
offonline
,
0
,
sizeof( 
offonline ) ); 
cin
>> n 
>>
m; 
for( 
int
i
=
1; 
i
<=
m; 
++
i ) 
{ 
cin
>>
e
[
i
].
u
>>
e
[
i
].
v; 
time
[
e
[
i
].
u
]
++
,
time
[
e
[
i
].
v
]
++; 
}
bool
f
=
true; 
for( 
int
i
=
1; 
i
<= n; 
++
i ) 
{ 
online
[
i
]
=
offonline
[
i
]
=
time
[
i
]
/
2; 
if( 
time
[
i
]
&
1 ) 
{ 
f
=
false; 
break; 
}
}
if( 
!
f ) 
{ 
cout
<<
0
<<
endl; 
continue; 
}
DFS( 
1 ); 
cout
<<
ans
<<
endl; 
}
return
0; 
}
/*
*/

转载于:https://www.cnblogs.com/crazyacking/p/4671395.html

你可能感兴趣的文章