感觉特别裸的搜索 想了半天的树形dp 然后发现规模是300 就去搜索
一层一层搜
#include<bits/stdc++.h> using namespace std; #define Max(x,y) (x)<(y)?(y):(x) #define Min(x,y) (x)<(y)?(x):(y) #define ll long long #define rg register const int N=500+5,M=1000000+5,inf=0x3f3f3f3f,P=9999973; const int power=4,base=10000; int n,m,ans=inf,mxd,dep[N],cure[N],f[N]; int vec[N][N],sz[N]; template <class t>void rd(t &x){ x=0;int w=0;char ch=0; while(!isdigit(ch)) w|=ch=='-',ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); x=w?-x:x; } int head[N],tot=0; struct edge{int v,nxt;}e[N<<1]; void add(int u,int v){ e[++tot]=(edge){v,head[u]},head[u]=tot; } void dfs1(int u,int fa){ dep[u]=dep[fa]+1,f[u]=fa,vec[dep[u]][++sz[dep[u]]]=u,mxd=Max(mxd,dep[u]); for(int i=head[u];i;i=e[i].nxt) if(e[i].v!=fa) dfs1(e[i].v,u); } void tag(int u,int col){ cure[u]=col; for(int i=head[u];i;i=e[i].nxt) if(e[i].v!=f[u]) tag(e[i].v,col); } int get_sum(int deep){ int sum=0; for(int i=1;i<=sz[deep];++i) if(!cure[vec[deep][i]]) ++sum; return sum; } void dfs2(int deep,int co){ if(co>=ans) return; if(deep>mxd||!get_sum(deep)){ ans=Min(ans,co); return; } for(int i=1,v;i<=sz[deep];++i){ v=vec[deep][i]; if(cure[v]) continue; tag(v,1); dfs2(deep+1,co+get_sum(deep)); tag(v,0); } } int main(){ freopen("in.txt","r",stdin); rd(n),rd(m); for(int i=1,u,v;i<=m;++i) rd(u),rd(v),add(u,v),add(v,u); memset(dep,0,sizeof(dep));dfs1(1,0); dfs2(2,1); printf("%d",ans); return 0; }