拿到这题看都没看直接写了个裸地贪心+并查集
写完就发现一点问题
using namespace std;
int n,m,g[40010];
struct pi
{
int p1,p2,ang;
}pe[100010];
bool cmp(pi aa,pi bb){return aa.ang>bb.ang;}int getf(int x){
if (g[x]==x) return x;
g[x]=getf(g[x]);
return g[x];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin>>n>>m;
for (int i=1;i<=20010;i++) g[i]=i;
for (int i=1;i<=m;i++) cin>>pe[i].p1>>pe[i].p2>>pe[i].ang;
sort(pe+1,pe+m+1,cmp);
int fa1=pe[1].p1,fa2=pe[1].p2,ans=0;
for (int i=2;i<=m;i++)
{
if (getf(pe[i].p1)==getf(pe[i].p2))
{printf("%d\n",pe[i].ang); return 0;}
else
{
if (g[pe[i].p1]==fa1) g[pe[i].p2]=fa2;
else if (g[pe[i].p1]==fa2) g[pe[i].p2]=fa1; else if (g[pe[i].p2]==fa1) g[pe[i].p1]=fa2; else if (g[pe[i].p2]==fa2) g[pe[i].p1]=fa1;
}
}
printf("%d\n",0);
return 0;
}
因为当 当前2个罪犯 都不在2个并查集中的时候 究竟是 p1加到fa1 还是 p2加到fa1 就不知道
如果随便加的话 可能后面的关系会对前面的关系产生影响 所以不能维护最优解
所以这个人品贪心也就过了3个点
最后想到正解
即建立并查集的补集 --> 将g数组扩大2倍 n+1~end 为补集
分别将p1 p2和p2 p1的补集合并
这样后面关系更新后前面的也会更新
所以这样做是正确的
然后按这个思路debug了一下就A了
下面是AC代码
using namespace std;
int n,m,g[40010];
struct pi
{
int p1,p2,ang;
}pe[100010];
bool cmp(pi aa,pi bb){return aa.ang>bb.ang;}int getf(int x){
if (g[x]==x) return x;
g[x]=getf(g[x]);
return g[x];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin>>n>>m;
for (int i=1;i<=2*n;i++) g[i]=i;
for (int i=1;i<=m;i++) cin>>pe[i].p1>>pe[i].p2>>pe[i].ang;
sort(pe+1,pe+m+1,cmp);
for (int i=1;i<=m;i++)
{
int x=getf(pe[i].p1),y=getf(pe[i].p2);
if (x==y){printf("%d\n",pe[i].ang); return 0;}
g[x]=getf(pe[i].p2+n); g[y]=getf(pe[i].p1+n);
}
printf("%d\n",0);
return 0;
}