做一个网站的建设流程,wordpress有哪些功能,公司网站建设排名,基于5G的网站设计题目大意
有n个问题#xff0c;m个人#xff0c;每个人可以解决一些问题#xff0c;问最少选多少个人可以解决所有问题 解题思路
如果一个人解决的问题被别的人包括#xff0c;那么可以把这个人丢掉
对于一个问题只能由一个人解决#xff0c;那么直接选这个人
然后枚举…题目大意
有n个问题m个人每个人可以解决一些问题问最少选多少个人可以解决所有问题 解题思路
如果一个人解决的问题被别的人包括那么可以把这个人丢掉
对于一个问题只能由一个人解决那么直接选这个人
然后枚举每个问题被谁解决即可 代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 100
using namespace std;
int n, m, x, y, g, pp, ans, tot, dg[N], uf[N], p[N], head[N], a[N][10];
struct rec
{int to, next;
}e[N*6];
void add(int x, int y)
{e[tot].to y;e[tot].next head[x];head[x] tot;
}
void dfs(int x, int y)
{if (y ans) return;if (x n){ans min(ans, y);return;}if (p[x]){dfs(x 1, y);return;}for (int i head[x]; i; i e[i].next)if (!uf[e[i].to]){for (int j 1; j a[e[i].to][0]; j)p[a[e[i].to][j]];dfs(x 1, y 1);for (int j 1; j a[e[i].to][0]; j)p[a[e[i].to][j]]--;}return;
}
int main()
{ ans 60;scanf(%d%d, n, m);for(int i 1; i m; i){scanf(%d, x);a[i][0] x;for (int j 1; j x; j){scanf(%d, a[i][j]);add(a[i][j], i);}sort(a[i] 1, a[i] 1 x);}for (int i 1; i m; i)for (int j 1; j m; j)//i包括j{if (i j) continue;pp 1;x 1;y 1;while(x a[i][0]){while (a[i][x] a[j][y] y a[j][0]) y;if (y a[j][0]) break;x;}if (y a[j][0]) pp 0;if (a[i][0] a[j][0] i j) pp 0;if (pp) uf[j] 1;}for (int i 1; i m; i)if (!uf[i])for (int j 1; j a[i][0]; j)dg[a[i][j]];for (int i 1; i n; i)if (dg[i] 1 !p[i])//只能由一个人解决{g;for (int j head[i]; j; j e[j].next)if (!uf[e[j].to]){for (int k 1; k a[e[j].to][0]; k)p[a[e[j].to][k]];}}dfs(1, g);printf(%d, ans);return 0;
}
