正題

---

題目大意

有$n$個點$m$條邊，若一個點沒選，那么連接到的點都得選擇。求最小選擇權值。

---

解題思路

對于每個聯通塊暴力$dfs$，若一個點不選那么就把別的點都選上。

因為每個點至少限制一個點，那么時間復雜度最壞為$O(2^{\frac{n}{2}})$(也就是一條鏈的情況)。

---

$code$

#include<cstdio> #include<algorithm> using namespace std; const int N=60; int tot,in[N],ans,w[N],flag[N],n,maxs,m,ls[N]; bool v[N],zh[N]; struct node{int to,next; }a[N*20]; void addl(int x,int y) {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot; } void dfs(int x) {in[++tot]=x;v[x]=1;for(int i=ls[x];i;i=a[i].next)if(!v[a[i].to])dfs(a[i].to); } void get_ans(int dep,int z) {if(z>maxs) return;if(dep>tot){maxs=min(maxs,z);return;}get_ans(dep+1,z+w[in[dep]]);if(!flag[in[dep]]&&!zh[in[dep]]){for(int i=ls[in[dep]];i;i=a[i].next)flag[a[i].to]++;get_ans(dep+1,z);for(int i=ls[in[dep]];i;i=a[i].next)flag[a[i].to]--;} } int main() {//freopen("graph.in","r",stdin);//freopen("graph.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&w[i]);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);addl(x,y);addl(y,x);if(x==y) zh[x]=1;}for(int i=1;i<=n;i++){maxs=2147483647;tot=0; if(v[i]) continue;dfs(i);get_ans(1,0);ans+=maxs;}printf("%d",ans); }

總結

以上是生活随笔為你收集整理的jzoj4252-QYQ的图【dfs】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。