NOI.AC NOIP模拟赛 第四场 补记
子图
题目大意：
一张\(n(n\le5\times10^5)\)个点，\(m(m\le5\times10^5)\)条边的无向图。删去第\(i\)条边需要\(w_i\)的代价。现在要通过删去一些边，使得剩下的满足对于这个图的任意一些点，这些点之间互联的边数小于这些点的总点数。求总代价最小值
思路：
不难发现答案为整张图代价和-最大生成森林代价和。
时间复杂度\(\mathcal O(m\alpha(n))\)。
源代码：
#include<cstdio>
#include<cctype>
#include<numeric>
#include<algorithm>
#include<functional>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
typedef long long int64;
const int N=5e5+1,M=5e5;
struct Edge {
int u,v,w;
bool operator > (const Edge &rhs) const {
return w>rhs.w;
}
};
Edge e[M];
class DisjointSet {
private:
int anc[N];
int find(const int &x) {
return x==anc[x]?x:anc[x]=find(anc[x]);
}
public:
void reset(const int &n) {
std::iota(&anc[1],&anc[n]+1,1);
}
void merge(const int &x,const int &y) {
anc[find(x)]=find(y);
}
bool same(const int &x,const int &y) {
return find(x)==find(y);
}
};
DisjointSet s;
int main() {
const int n=getint(),m=getint();
int64 ans=0;
for(register int i=0;i<m;i++) {
e[i].u=getint();
e[i].v=getint();
e[i].w=getint();
ans+=e[i].w;
}
s.reset(n);
std::sort(&e[0],&e[m],std::greater<Edge>());
for(register int i=0;i<m;i++) {
const int &u=e[i].u,&v=e[i].v,&w=e[i].w;
if(!s.same(u,v)) {
s.merge(u,v);
ans-=w;
}
}
printf("%lld\n",ans);
return 0;
}
Erlang
题目大意：
一共有\(n(n\le5\times10^5)\)个可重集\(S_i(\sum|S_i|\le5\times10^5)\)，每次可以选择一个非空集合，从里面随机抽取一个数，然后把这个数从集合中删掉。当存在两次抽取出来的数相等时结束。求最坏情况下，操作次数的最小值。
思路：
一个结论是，一定存在一种方案，使得总共只抽取两个集合，而且是先抽第一个抽了若干次后再去抽第二个。或者是只抽一个结合。
对于只抽一种集合的情况，直接用抽屉原理算即可。
因此，我们可以将数\(k\)在\(x\)中的最坏抽取次数记作\(c_{k,x}\)，对于每个数\(k\)，维护最小值和次小值。
枚举第一个集合\(x_1\)，将其中的每个数按照在第二个集合中最小抽取次数次数从大到小排序，抽取次数第\(i\)大的数的抽取次数为\(f_i\)，答案就是\(\min\{f_i+i\}\)。
时间复杂度\(\mathcal O(\sum|S_i|\log\sum|S_i|)\)。
源代码：
#include<cstdio>
#include<cctype>
#include<climits>
#include<algorithm>
#include<functional>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
const int N=5e5+1;
int a[N],b[N],k[N],cnt[N],num[N],min[N][2],f[N];
int main() {
const int n=getint();
num[0]=INT_MAX;
for(register int i=a[0]=1;i<=n;i++) {
b[i]=a[0];
k[i]=getint();
for(register int j=0;j<k[i];j++) {
a[a[0]++]=getint();
}
std::sort(&a[b[i]],&a[a[0]]);
num[i]=std::unique(&a[b[i]],&a[a[0]])-&a[b[i]];
for(register int j=b[i];j<b[i]+num[i];j++) {
int tmp=i;
if(num[tmp]<num[min[a[j]][0]]) std::swap(tmp,min[a[j]][0]);
if(num[tmp]<num[min[a[j]][1]]) std::swap(tmp,min[a[j]][1]);
}
}
for(register int i=1;i<a[0];i++) cnt[a[i]]++;
for(register int i=1;i<a[0];i++) {
if(cnt[a[i]]>1) goto Next;
}
puts("-1");
return 0;
Next:
if(n==1) {
printf("%d\n",num[1]+1);
return 0;
}
int ans=INT_MAX;
for(register int i=1;i<=n;i++) {
if(k[i]!=num[i]) ans=std::min(ans,num[i]+1);
for(register int j=1;j<=num[i];j++) {
f[j]=num[min[a[b[i]+j-1]][0]!=i?min[a[b[i]+j-1]][0]:min[a[b[i]+j-1]][1]];
}
std::sort(&f[1],&f[num[i]]+1,std::greater<int>());
for(register int j=1;j<=num[i];j++) {
if(f[j]!=INT_MAX) ans=std::min(ans,f[j]+j);
}
}
printf("%d\n",ans);
return 0;
}