+1 25pts暴力
按照35pts的暴力写的
by PlayerMo @ 2023-11-15 21:45:04
前 $25$ 分暴力
```cpp
#include<bits/stdc++.h>
#define debug(x,c) cerr<<#x<<' '<<x<<c
#define int long long
using namespace std;
const int N = 5e5+5, M = 1e6+5;
const int mod = 1e9+7;
int p2[M];
void init(int m) {
p2[0]=1;
for(int i=1;i<=m;++i)
p2[i]=p2[i-1]*2,
p2[i]%=mod;
}
int pow2(int k) { return p2[k]; }
int n,m;
struct node {
int to,nx;
} eg[M<<1];
int hd[N],tot;
void adeg(int u,int v) {
eg[++tot]={v,hd[u]};
hd[u]=tot;
}
void add(int &x,int y) {
x+=y;
x%=mod;
}
namespace bruteforce {
int vis,v;
bitset<64> ave;
void dfs(int u) {
vis|=1<<u;
for(int i=hd[u];i;i=eg[i].nx) {
if(ave[i]) continue;
int to=eg[i].to;
if(vis&(1<<to)) continue;
dfs(to);
}
}
void solve() {
int res=0;
for(int i=1;i<(1<<n);++i) {
int st;
int v=i<<1;
for(int j=1;j<=n;++j)
if(i&(1<<j-1)) st=j;
int num=0;
for(int i=1;i<=m;++i) {
ave[i*2]=ave[i*2-1]=1;
vis=0;
dfs(st);
vis&=v;
if(vis==v) num+=1;
ave[i*2]=ave[i*2-1]=0;
} add(res,pow2(num));
// cout<<i<<' '<<num<<' '<<pow2(num)<<'\n';
} cout<<res<<'\n';
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
init(m);
for(int i=1;i<=m;++i) {
int u,v;
cin>>u>>v;
adeg(u,v),
adeg(v,u);
}
bruteforce::solve();
return 0;
}
```
by abensyl @ 2023-11-15 21:45:42
我刚发的代码里面二进制压缩比较多，需要仔细阅读
by abensyl @ 2023-11-15 21:46:33
几个WA
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll n,m;
const ull modd=1000000007;
//unordered_map<pair<long long,long long> ,vector<vector<ll> > > gg;
vector<vector<ll> > a;
set<ll> choices;
vector<ll> ways;
ll ans=0;
void t_bug_s(string s){
cout<<s;
return;
}
void t_bug_i(ll s){
cout<<s;
return ;
}
/*
void dfs(ll desti,ll last,ll start){
for(auto &iter: a[last]){
ways.push_back(iter);//²»°üÆðµã£¡£¡£¡
if(iter==desti){
gg[{start,desti}].push_back(ways);
return;
}
dfs(desti,iter,start);
ways.pop_back();
}
return ;
}
ll meiju2(){
for
}
ll go(){
for(ll iter=0;iter<choices.size()-1;iter++){
for(ll iter2=iter+1;iter2<choices.size();iter2++){
dfs(iter2,iter,iter);
}
}
}
*/
/*
void go(){
sort(choices.begin(),choices.end());
ll sizeto=choices.back()-choices.front();
ll sizeres=(n-1)-sizeto;
ans+=(1<<sizeres);//????
return ;
}*/
ull quickpow(ll di,ll zhi){
if(zhi==1) return di;
if(zhi==0) return 1;
if(zhi%2==0)
{
ll og=quickpow(di,zhi/2);
return og*og;
}
else{
ll occ=quickpow(di,(zhi-1)/2);
return occ*occ*di;
}
}
pair<ll,ll> forbidden;
bitset<500009> vis;//!!!!!
//贪心
void meiju_edges(ll);
void dfs(ll,ll);
void meiju(ll p,ll num){
if(num==n+1) return ;
set<ll> tmp;
/*t_bug_s("CHOICES: ");
for(auto itt : choices){
t_bug_i(itt);
t_bug_s(" ");
}
t_bug_s("\n");
*/
for(;p<=n;p++){
// cout<<p<<endl;
tmp=choices;
choices.insert(p);
if(num!=1){
meiju_edges(p);
}
meiju(p+1,num+1);
choices=tmp;
}
return ;
}
//set<ll> cou;
//vector<vector<bool> > check;
bool ck(){
for(auto iter : choices){
if(!vis[iter]) return false;
}
return true;
}
void meiju_edges(ll p){
ll tmp1=-1;
ll fang=0;
ll tmp;
ll tmp2;
for(ll i=1;i<=n;i++){
for(ll j=0;j<a[i].size();j++){
if(a[i][j]>i) continue;
//先小后大
forbidden.second=i;
forbidden.first=a[i][j];
// if(check[i][a[i][j]]) continue;
// //!!!
// check[i][a[i][j]]=1;
// check[a[i][j]][i]=1;
//给双边加标记！
/* t_bug_s("DEL: ");
t_bug_i(i);
t_bug_s(" ");
t_bug_i(a[i][j]);
t_bug_s("\n");
*/
//cou.clear();
/* tmp=a[i][j];
a[i][j]=-1;*/
for(ll k=1;k<=n;k++){
vis[k]=0;
}
dfs(p,p);
/* a[i][j]=tmp;*/
if(ck()){
fang++;
}
}
}
//统计
ans+=(1<<(fang));
return ;
}
void dfs(ll now,ll last){
/* t_bug_i(last);
t_bug_s(" ");
t_bug_i(now);
t_bug_s("\n");*/
// if(choices.count(now)==1){
// cou.insert(now);
// }
vis[now]=1;
ll one,two;
for(auto iter: a[now]){
if(iter==last) continue;
one=min(iter,now);
two=max(iter,now);
if(one==forbidden.first && two==forbidden.second){
continue;
}
if(vis[iter]) continue;
dfs(iter,now);
}
return ;
}
int main(){
// freopen("barrack.txt","r",stdin);
// freopen("barrack.out","w",stdout);
//ios::sync_with_stdio(0);
// cout.tie(0);
//cin.tie(0);
cin>>n>>m;
ll u,v;
a.resize(n+2);
for(ll i=1;i<=m;i++){
cin>>u>>v;
a[u].push_back(v);
a[v].push_back(u);
//???!!!
}
/*check.resize(n+9);
for(ll i=1;i<=n;i++){
check[i].resize(n+9);
for(ll j=1;j<=n;j++){
if(i==j) continue;
check[i][j]=0;
}
//???!!!
}
*/
//<<k 2^k
// t_bug_i(1145);
meiju(1,1);
ans+=(n)*(1<<(m));
// ans+=n*quickpow(2,m);
cout<<ans;
return 0;
}
```
by PlayerMo @ 2023-11-15 21:48:00
@[abensyl](/user/641163) @[PlayerMo](/user/525590) 感谢
为什么我第二个样例跑出来比答案小
Code:
```c
#include<bits/stdc++.h>
#define N 500005
using namespace std;
int n,m,h[N],idx=1;//从1开始
struct edge{
int v,to;
}e[2*N];
void ade(int u,int v){
e[++idx] = {v,h[u]};
h[u] = idx;
}
int cnt=0,ans,flag[N];
void dfs(int u,int sn,int sm){ //点的状态为sn,边的状态为sm，检查能否联通所有军营
flag[u] = 1;
// printf("%d %d %d %d\n",u,fa,sn,sm);
if(1<<(u-1)&sn) cnt++; //当前点是军营
for(int i=h[u];i;i=e[i].to){
int ne = e[i].v;
int t = i/2; //对应的二进制位
// printf("i=%d t=%d\n",i,t);
if((1<<(t-1)&sm) || flag[ne]) continue;
dfs(ne,sn,sm);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v; scanf("%d%d",&u,&v);
ade(u,v); ade(v,u);
}
int fulln = (1<<n)-1,fullm = (1<<m)-1,nook=0;
for(int i=1;i<=fulln;i++){ //第k位是否是军营
for(int j=0;j<=fullm;j++){ //第几位为4代表边 (2*i) (2*i+1)没有看守
for(int k=1;k<=n;k++) flag[k] = 0;
int pos = 0,cnti = 0; //当前状态一共几个军营
cnt = 0;
for(int k=1;k<=n;k++){
if((1<<(k-1))&i){
cnti++;
pos = k;
}
}
// printf("i=%d j=%d\n\n",i,j);
dfs(pos,i,j);
if(cnt == cnti) ans++;
else{
nook++;
printf("case:%d %d notok>>%d\n",i,j,nook);
bitset<5>ii = i;
cout<<ii<<endl;
bitset<5>jj = j;
cout<<jj<<endl;
cout<<endl;
}
}
}
printf("%d",ans);
return 0;
}
```
by Zak_chen @ 2023-11-15 22:08:26
我的加一个取模就35pts了//
by PlayerMo @ 2023-11-15 22:11:15
@[PlayerMo](/user/525590) orz
by Zak_chen @ 2023-11-15 22:12:54