CF95ELuckyCountry并查集+dp

题目大意&＃xff1a;
如果一个数中不包含除4和7之外的数字则是幸运数。有n个岛屿&＃xff0c;通过双向道路连接。这些岛屿被分为几个地区。每个岛属于恰好一个区域&＃xff0c;同一区域中的任何两个岛之间存在道路&＃xff0c;不同区域的任何两个岛之间没有路径。如果一个地区的岛屿数量是一个幸运数字&＃xff0c;则这个地区是幸运的。问最少增加几条道路能创建一个幸运地区。

分析&＃xff1a;
首先跑出每个地区的大小&＃xff0c;因为边是双向的&＃xff0c;所以不用连通分量&＃xff0c;直接上并查集去维护即可。假设每个连通块的大小为xixi&＃xff0c; 现在问题就变成问最少要用多少个xixi可以组成一个幸运数字了。因为题目要求的是连接的次数&＃xff0c;所以把这个答案减11即可。

我们发现所有数字的和是等于n" role="presentation" >n$n$的&＃xff0c;所以可以用dp&＃xff0c;设f[i][j]f[i][j]为前i个数&＃xff0c;组成和为jj的数，设第i个数为ai" role="presentation" >ai$a_i$&＃xff0c;最小要用多少个数&＃xff0c;有

代码&＃xff1a;

#include
#include
#include
#include const int maxn&＃61;1e5&＃43;7;using namespace std;int n,m,cnt,x,y;
int p[maxn],f[maxn],b[maxn],size[maxn],w[maxn],v[maxn];int find(int x)
{int y&＃61;x,root;while (p[x]) x&＃61;p[x];root&＃61;x;x&＃61;y;while (p[x]){y&＃61;p[x];p[x]&＃61;root;x&＃61;y;}return root;
}void uni(int x,int y)
{int u&＃61;find(x);int v&＃61;find(y);if (u&＃61;&＃61;v) return;if (size[x]>size[y]) p[v]&＃61;u,size[u]&＃43;&＃61;size[v];else p[u]&＃61;v,size[v]&＃43;&＃61;size[u];
}bool check(int x)
{while (x>0){if ((x%10!&＃61;4) && (x%10!&＃61;7)) return false;x/&＃61;10;}return true;
}int main()
{scanf("%d%d",&n,&m);for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) size[i]&＃61;1; for (int i&＃61;1;i<&＃61;m;i&＃43;&＃43;){scanf("%d%d",&x,&y);uni(x,y);} for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){if (find(i)&＃61;&＃61;i) b[size[i]]&＃43;&＃43;;} memset(f,0x3f3f3f3f,sizeof(f));f[0]&＃61;0; for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){if (!b[i]) continue;int sum&＃61;1,power&＃61;1,k&＃61;1;w[&＃43;&＃43;cnt]&＃61;i;v[cnt]&＃61;1;while (sum2;sum&＃43;&＃61;power;if (sum>&＃61;b[i]){sum-&＃61;power;w[&＃43;&＃43;cnt]&＃61;i*(b[i]-sum);v[cnt]&＃61;b[i]-sum;break;}w[&＃43;&＃43;cnt]&＃61;i*power;v[cnt]&＃61;power;}} for (int i&＃61;1;i<&＃61;cnt;i&＃43;&＃43;){for (int j&＃61;n;j>&＃61;0;j--){if (j-w[i]>&＃61;0)f[j]&＃61;min(f[j],f[j-w[i]]&＃43;v[i]);}} int ans&＃61;0x3f3f3f3f; for (int i&＃61;4;i<&＃61;n;i&＃43;&＃43;){if (check(i)){ans&＃61;min(ans,f[i]-1);}}if (ans>n) printf("-1");else printf("%d",ans);
}