做校园网站,教育+wordpress模板,徐州自助建站软件,新型门窗网站模板题目链接#xff1a;... 思路#xff1a; 优化搜索顺序#xff0c;用DFS按照bfs的思想#xff0c;从每一层开始搜索#xff0c;枚举删边。 对于分层#xff0c;dfs预处理一下就好了。 代码#xff1a; #includeiostream
#includecstdio
#includecst…题目链接... 思路 优化搜索顺序用DFS按照bfs的思想从每一层开始搜索枚举删边。 对于分层dfs预处理一下就好了。 代码 #includeiostream
#includecstdio
#includecstring
#includealgorithm
#includecmath
#define R register
#define ll long long int
using namespace std;
const int N1015;
struct E{int nxt,to;
}e[N];
int n,p,num,ans0x3f3f3f3f,shen,head[N],dep[N],ren[N][N],f[N],tim[N],flag[N];
inline void add(R int u,R int v){e[num].nxthead[u];e[num].tov;head[u]num;
}
inline void dfs1(R int pos,R int fa){dep[pos]dep[fa]1;shenmax(shen,dep[pos]);f[pos]fa;ren[dep[pos]][tim[dep[pos]]]pos;//当前深度 第几个 是什么for(R int ihead[pos];i;ie[i].nxt){R int ve[i].to;if(v!fa)dfs1(v,pos);}
}
inline int check(R int depth){for(R int j1;jtim[depth];j)if(flag[f[ren[depth][j]]])return 0;return 1;
}
inline void dfs(R int depth,R int tot){//深度 第几个if(totans)return;if(check(depth)){ansmin(ans,tot);return;}for(R int j1;jtim[depth];j){if(flag[f[ren[depth][j]]]){flag[ren[depth][j]]1;tot;}}for(R int i1;itim[depth];i){//枚举删边if(flag[f[ren[depth][i]]]){flag[ren[depth][i]]0;--tot;dfs(depth1,tot);flag[ren[depth][i]]1;tot;}}for(R int j1;jtim[depth];j)if(flag[f[ren[depth][j]]])flag[ren[depth][j]]0;
}
int main(){scanf(%d%d,n,p);for(R int i1;ip;i){R int u,v;scanf(%d%d,u,v);add(u,v);add(v,u);}dfs1(1,0);flag[1]1;dfs(2,1);if(ans0x3f3f3f3f)printf(1);elseprintf(%d,ans);return 0;
} 转载于:https://www.cnblogs.com/sky-zxz/p/9842747.html
