#搜索，剪枝，网络流，最大匹配#ssl 2123 民生问题

本文主要是介绍#搜索，剪枝，网络流，最大匹配#ssl 2123 民生问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

~~后两个是吸引你点进来的，根本不存在~~

题目

在这里插入图片描述

分析

其实是正解应该是网络流的题目，这里用深搜+剪枝实现
1.深搜时找到比当前最优解不优的答案直接退出
2.预处理可以不需要的专家（有专家完全替代他）
3.对于问题只有一个专家能解决的，该专家必选，该专家的会的其他问题可以标记不需要

代码

#include <cstdio>
#define rr register
using namespace std;
int m,n,ans,p[61][61],a[61][7],b[61],v[61],now; bool e[61][61];
inline void dfs(int dep,int now){if (now>=ans) return;//不可能更优if (dep>m){//选完问题了ans=now;return;}for (rr int i=1;i<=p[dep][0];++i){rr int t=p[dep][i];for (rr int j=1;j<=a[t][0];++j) ++v[a[t][j]];//选择该专家rr int j=dep+1; while (v[j]) ++j; dfs(j,now+1);//下一个问题的位置for (rr int j=1;j<=a[t][0];++j) --v[a[t][j]];//回溯}
}
signed main(){scanf("%d%d",&m,&n); ans=n;for (rr int i=1;i<=n;++i){scanf("%d",&a[i][0]);for (rr int j=1;j<=a[i][0];++j)scanf("%d",&a[i][j]),e[i][a[i][j]]=1;}for (rr int i=1;i<=n;++i)for (rr int j=1;j<=n;++j)if (i!=j&&!b[i]&&!b[j]){rr int flag=1;for (rr int k=1;k<=m&&flag;++k)flag=!e[i][k]||e[j][k];b[i]=flag;//找出能够不要的科学家}for (rr int i=1;i<=n;++i)if (!b[i])for (rr int j=1;j<=a[i][0];++j)p[a[i][j]][++p[a[i][j]][0]]=i;for (rr int i=1;i<=m;++i)if (p[i][0]==1&&!b[p[i][1]]){//只有一个科学家会for (rr int j=1;j<=a[p[i][1]][0];++j) ++v[a[p[i][1]][j]];b[p[i][1]]=1; ++now;}rr int t=1; while (v[t]) ++t;dfs(t,now); printf("%d",ans);return 0;
}