考试的时候看少了一行,导致暴力都写错额…

贾教说他出的这题水,但是我觉得并不水,那个结论还是很神的。

首先M(i)就是i的最小生成树的最大边,

设f[i]表示i属于哪个集合

我们把边按权值从小到大排序,对于一条边(u,v),权值为w,

如果w<=min(M(f[u])+Z[C[f[u]]],M(f[v])+Z[C[f[v]]]),

那么u,v就不能分开,否则不满足“半完美”这个条件,那就把它们放入一个集合。

搞完之后扫一遍输出每个集合即可。

至于怎么证明正确性,我也不知道。

#include<cstdio>
#include<algorithm>
#define N 100010
using namespace std;
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
struct pp{int u,v,w;}a[500010];
inline bool cmp(pp a,pp b){return a.w<b.w;}
int n,m,i,j,z[N],M[N],c[N],f[N],ed,g[N],nxt[N<<1],v[N<<1],k,cnt[N];
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
void go(int x,int pre,int y){
f[x]=y;
for(int i=g[x];i;i=nxt[i])if(v[i]!=pre)go(v[i],x,y);
}
inline void link(int x,int y,int z){
if(f[x]==f[y])return;
if(c[f[x]]>c[f[y]])swap(x,y);
c[f[y]]+=c[f[x]];M[f[y]]=z;
go(x,0,f[y]);
add(x,y);add(y,x);
}
int main(){
read(n);read(m);
for(i=1;i<=n;i++)read(z[i]);
for(i=1;i<=m;i++)read(a[i].u),read(a[i].v),read(a[i].w);
sort(a+1,a+m+1,cmp);
for(i=1;i<=n;i++)f[i]=i,c[i]=1;
for(i=1;i<=m;i++)if(a[i].w<=min(M[f[a[i].u]]+z[c[f[a[i].u]]],M[f[a[i].v]]+z[c[f[a[i].v]]]))link(a[i].u,a[i].v,a[i].w);
for(i=1;i<=n;i++)g[i]=0;
ed=0;
for(i=1;i<=n;i++){
if(!cnt[f[i]])k++;
cnt[f[i]]++;
add(f[i],i);
}
for(printf("%d\n",k),i=1;i<=n;i++)if(cnt[i]){
for(printf("%d",cnt[i]),j=g[i];j;j=nxt[j])printf(" %d",v[j]);
puts("");
}
return 0;
}

  

05-11 13:32