拿到这题看都没看直接写了个裸地贪心+并查集
写完就发现一点问题
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> 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代码
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> 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; }
