首页 > 代码库 > 议员秘密 题解
议员秘密 题解
3．议员秘密
（secret.pas/c/cpp）
【问题描述】
某国有N个议员，大佬XDD要从中选出来一部分一起喝茶谈一些事情。某两个议员之间可能存在矛盾，大佬XDD不希望选出来的这些议员之间有任何矛盾关系，以至于喝喝茶的场面搞得很尴尬。
.png)
已知这些议员之间存在M对矛盾关系，你能否帮助大佬XDD计算出他最多可以选出多少个议员来喝茶谈事情？
如果聪明的你把议员看成点，把矛盾关系看成无向边，那么题目中的数据保证M对矛盾所构成的图中不存在含有超过3个点的环。（图1符合要求，图2则不符合）
【输入数据】
输入文件的第一行是用空格隔开的两个整数N和M，表示一共有N个议员，这些议员之间有M对矛盾关系。接下来的M行，每行将有一对整数a和b（用空格隔开），表示议员a与议员b有矛盾。输入数据保证不含重边和自环。（议员的编号都是从1开始的）
【输出数据】
输出一行，包含一个整数，即大佬XDD最多可以选出多少议员来喝茶谈事情。
【输入输出样例】
secret.in
5 6
1 2
3 2
1 3
3 5
3 4
4 5
secret.out
2
【样例说明】
某国有6个议员，矛盾关系中1 - 2 - 3组成一个环，3 - 4 - 5组成一个环，因此只能在这两个环中分别选一个议员，并且不能选择3号议员。
【数据规模与约定】
对于20%的数据，1 ≤ N ≤ 20
对于40%的数据，1 ≤ N ≤ 50
对于100%的数据，1 ≤ N ≤ 200
输入数据保证合法。
————————————————————我是分割线————————————————————————
dp题目。据说是树状（仙人掌？？？）。
dp[i][j]表示第i个点，选（j==1）或不选（j==0）的情况。
注意题目没有保证联通，有可能是森林。
写的记忆化搜索，代码如下：
1 /* 2 Problem: 3 OJ: 4 User: S.B.S. 5 Time: 6 Memory: 7 Length: 8 */ 9 #include<iostream>10 #include<cstdio>11 #include<cstring>12 #include<cmath>13 #include<algorithm>14 #include<queue>15 #include<cstdlib>16 #include<iomanip>17 #include<cassert>18 #include<climits>19 #include<functional>20 #include<bitset>21 #include<vector>22 #include<list>23 #define F(i,j,k) for(register int i=j;i<=k;++i)24 #define M(a,b) memset(a,b,sizeof(a))25 #define FF(i,j,k) for(register int i=j;i>=k;i--)26 #define maxn 21027 #define inf 0x3f3f3f3f28 #define maxm 400129 #define mod 99824435330 #define LOCAL31 using namespace std;32 int read(){33 int x=0,f=1;char ch=getchar();34 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}35 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}36 return x*f;37 }38 int n,m;39 int fa[maxn],dp[maxn][2];40 bool tree[maxn][maxn];41 bool vis[maxn],mp[maxn][maxn];42 inline void dfs(int u)43 {44 vis[u]=true;45 F(i,1,n){46 if(!vis[i]&&mp[u][i]){47 tree[u][i]=1;48 fa[i]=u;49 dfs(i);50 }51 }52 }53 inline int solve(int u,int v)54 {55 int cnt;56 if(dp[v][u]!=-1) return dp[v][u];57 if(u==0){58 cnt=0;59 F(i,1,n) if(tree[v][i]) cnt+=max(solve(0,i),solve(1,i));60 return dp[v][u]=cnt;61 }62 else{63 bool temp[maxn];M(temp,0);64 F(i,1,n){65 if(tree[v][i]){66 temp[i]=true;67 F(j,1,n) if(tree[i][j]&&mp[v][j]) temp[j]=true;68 }69 }70 cnt=0;71 F(i,1,n) if(!temp[i]&&fa[i]!=-1&&temp[fa[i]])72 cnt+=max(solve(0,i),solve(1,i));73 return dp[v][u]=cnt+1;74 }75 }76 int ans;77 int main()78 {79 std::ios::sync_with_stdio(false);//cout<<setiosflags(ios::fixed)<<setprecision(1)<<y;80 #ifdef LOCAL81 freopen("input.txt","r",stdin);82 freopen("output.txt","w",stdout);83 #endif84 cin>>n>>m;85 M(dp,-1);M(fa,-1);86 F(i,1,m){int a,b;cin>>a>>b;mp[a][b]=mp[b][a]=1;}87 F(i,1,n){88 if(!vis[i]){89 dfs(i);90 ans+=max(solve(0,i),solve(1,i));91 }92 }93 cout<<ans<<endl;94 return 0;95 }
议员秘密 题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。