QAQ的图 本 题 时 间 复 杂 度 玄 学 ， 其 实 暴 力 就 可 以 过 ， 暴 力 ， 就 是 把 每 个 点 枚 举 可 不 可 以 选 ， 时 间 有 O ( 2 n ) , 所 以 肯 定 是 不 行 ， 而 我 们 加 一 个 优 化 ， 一 个 点 可 以 不 选 当 且 仅 当 与 他 相 连 的 点 没 有 一 个 不 选 ， 这 样 时 间 就 优 化 成 O ( 2 n / 2 ) ， n < = 50 , 所 以 能 过 本题时间复杂度玄学，其实暴力就可以过，暴力，就是把每个点枚举可不可以选，时间有O(2^n),所以肯定是不行，而我们加一个优化，一个点可以不选当且仅当与他相连的点没有一个不选，这样时间就优化成O(2^{n/2})，n<=50,所以能过 本题时间复杂度玄学，其实暴力就可以过，暴力，就是把每个点枚举可不可以选，时间有O(2n),所以肯定是不行，而我们加一个优化，一个点可以不选当且仅当与他相连的点没有一个不选，这样时间就优化成O(2n/2)，n<=50,所以能过
————————————————————————————————————— 这题有个坑点，因为会有自环，而自环是必须被选的
#include<bits/stdc++.h> using namespace std; const int N=55,M=510; int n,m,val[N],need[N]; struct mess{ int v,link; }q[M*2]; int link[N][N],now[N],head[N],cnt=0,ansout=500010,ans=0; void put(int u,int v){q[++cnt].v=v;q[cnt].link=head[u];head[u]=cnt;} void dfs(int s){ if(ans>=ansout){return;} if(s==n){ ansout=min(ansout,ans); return; } ans+=val[s+1];dfs(s+1);ans-=val[s+1]; if(!now[s+1]){ for(int i=head[s+1];i;i=q[i].link){ int v=q[i].v; now[v]++; } dfs(s+1); for(int i=head[s+1];i;i=q[i].link){ int v=q[i].v; now[v]--; } } } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&val[i]); } for(int j=1;j<=m;j++){ int u,v; scanf("%d%d",&u,&v); if(u==v) now[u]++; if((!link[u][v])) put(u,v),put(v,u),need[u]++,need[v]++;link[u][v]=1,link[v][u]=1; } dfs(0); printf("%d",ansout); }