題干：

鏈接：https://ac.nowcoder.com/acm/contest/885/E
來源：牛客網
?

Note:?For C++ languages, the memory limit is 100 MB.?For other languages, the memory limit is 200 MB.

?

In graph theory, an independent set is a set of nonadjacent vertices in a graph. Moreover, an independent set is maximum if it has the maximum cardinality (in this case, the number of vertices) across all independent sets in a graph.

An induced subgraph G'(V', E') of a graph G(V, E) is a graph that satisfies:

* V′?VV' \subseteq VV′?V

* edge (a,b)∈E′(a,b) \in E'(a,b)∈E′ if and only if a∈V′,b∈V′a \in V', b \in V'a∈V′,b∈V′, and edge (a,b)∈E(a, b) \in E(a,b)∈E;


Now, given an undirected unweighted graph consisting of n vertices and m edges. This problem is about the cardinality of the maximum independent set of each of the 2n2^n2n possible induced subgraphs of the given graph. Please calculate the sum of the 2n2^n2n such cardinalities.

?

輸入描述:

The first line contains two integers n and m (2≤n≤26,0≤m≤n×(n?1)22 \le n \le 26, 0 \le m \le \frac{n \times (n-1)}{2}2≤n≤26,0≤m≤2n×(n?1)?) --- the number of vertices and the number of edges, respectively. Next m lines describe edges: the i-th line contains two integers xi,yix_i, y_ixi?,yi? (0≤xi<yi<n0 \le x_i < y_i < n0≤xi?<yi?<n) --- the indices (numbered from?0 to n - 1) of vertices connected by the i-th edge.The graph does not have any self-loops or multiple edges.

輸出描述:

Print one line, containing one integer represents the answer.

示例1

輸入

復制

3 2 0 1 0 2

輸出

復制

9

說明

The cardinalities of the maximum independent set of every subset of vertices are: {}: 0, {0}: 1, {1}: 1, {2}: 1, {0, 1}: 1, {0, 2}: 1, {1, 2}: 2, {0, 1, 2}: 2. So the sum of them are 9.

示例2

輸入

復制

7 5 0 5 3 4 1 2 2 5 0 2

輸出

復制

328

題目大意：

給一個n個點m條邊的無向圖，求所有子圖（包括本身）的最大獨立集元素個數之和。（2<=n<=26）

解題報告：

直接狀壓dp，求出對于每一個子圖的最大獨立集的元素之和就可以了。

轉移方程：dp[sta]=max(dp[最大獨立集不包含這個點],dp[包含這個點])。

然后卡空間，所以要char類型。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 1<<26; int b[MAX]; char p[MAX],dp[MAX]; int n,m; int main() {cin>>n>>m;int ans = 0;for(int u,v,i = 1; i<=m; i++) {scanf("%d%d",&u,&v);b[u] |= 1<<v;b[v] |= 1<<u; }dp[0] = 0;for(int sta = 1; sta < (1<<n); sta++) {int x = __builtin_ffs(sta);x--;dp[sta] = max((int)dp[sta-(1<<x)],dp[sta - (1<<x) - (sta & b[x])] + 1);ans += dp[sta];}printf("%d\n",ans);return 0 ; }

?

總結

以上是生活随笔為你收集整理的【2019牛客暑期多校训练营（第五场）- E】independent set 1（最大独立集，状压dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

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