长沙哪家公司做网站,vue使用于网站开发,成都电子商务网站,新手怎么做网站内容维护正题 题目大意
有nnn个点mmm条边#xff0c;若一个点没选#xff0c;那么连接到的点都得选择。求最小选择权值。 解题思路
对于每个联通块暴力dfsdfsdfs#xff0c;若一个点不选那么就把别的点都选上。
因为每个点至少限制一个点#xff0c;那么时间复杂度最坏为O(2n2)O…正题 题目大意
有nnn个点mmm条边若一个点没选那么连接到的点都得选择。求最小选择权值。 解题思路
对于每个联通块暴力dfsdfsdfs若一个点不选那么就把别的点都选上。
因为每个点至少限制一个点那么时间复杂度最坏为O(2n2)O(2^{\frac{n}{2}})O(22n)(也就是一条链的情况)。 codecodecode
#includecstdio
#includealgorithm
using namespace std;
const int N60;
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].toy;a[tot].nextls[x];ls[x]tot;
}
void dfs(int x)
{in[tot]x;v[x]1;for(int ils[x];i;ia[i].next)if(!v[a[i].to])dfs(a[i].to);
}
void get_ans(int dep,int z)
{if(zmaxs) return;if(deptot){maxsmin(maxs,z);return;}get_ans(dep1,zw[in[dep]]);if(!flag[in[dep]]!zh[in[dep]]){for(int ils[in[dep]];i;ia[i].next)flag[a[i].to];get_ans(dep1,z);for(int ils[in[dep]];i;ia[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 i1;in;i)scanf(%d,w[i]);for(int i1;im;i){int x,y;scanf(%d%d,x,y);addl(x,y);addl(y,x);if(xy) zh[x]1;}for(int i1;in;i){maxs2147483647;tot0; if(v[i]) continue;dfs(i);get_ans(1,0);ansmaxs;}printf(%d,ans);
}
