关于这道题,本菜狗在阅读各位大佬的题解后终于大彻大悟,顺利ac,在此先感谢各位大佬的题解。 根据题目要求,我们需要将囚犯产生的冲突的影响力的最大值降到最小,这里有那么点贪心和二分答案的味道。这道题的标签是并查集,那么该如何使用并查集求解呢?
我们首先将冲突的情况保存在结构体数组里,并将其从大到小排序,再进行逐个处理。当我们处理每一次冲突时,它都是当前剩余为处理冲突的影响力最大值。若当前冲突的两位囚犯可以分开,那么冲突就被避免,反之,两位囚犯无法分开,那么该次冲突的影响力即为所有产生的冲突的最大值(更大的已经被避免了)。
如何判断会产生冲突的囚犯能否被分开,这里我们用到了并查集。举一个栗子:对于某一对产生冲突的囚犯a、b,a,b互相视对方为敌人,本着敌人的敌人可以成为敌人的原则,我们安排b与a的敌人们关押在一起,b与a的敌人们关押在一起(也就是并查集里面的合并步骤),这样便能避免这次冲突。当然,如果我们发现a、b(a、b分别在之前与其他人存在冲突,已经被安排了)已经住在一起了,那对不起了,a、b只能干架了,这里体现的就是并查集的查找步骤,查看a,b是否在同一个集合(监狱)里。由于之前已经按照冲突的影响力降序排序了,本次冲突即为影响力最大值,也就是答案。
以下是代码:
using namespace std;
typedef long long ll;
typedef pair<int ,int > PII;
const int N = 2e5+5 , mod = 998244353 , INF = 1e9;
int n,m;
int pre[N];//存放父节点
int enemy[N];//用于记录某个囚犯的敌人
struct conflict{//用于记录冲突情况的结构体
int a,b;
ll c;
}x[N];
void init()//初始化
{
for(int i=1;i<=n;i++)
{
pre[i]=i;
}
}
int find(int x)//查找+路径压缩
{
if(pre[x]==x) return x;
else return pre[x]=find(pre[x]);
}
void join(int x,int y)//合并
{
int fx=find(x),fy=find(y);
if(fx==fy) return ;
else{
pre[fx]=fy;
}
}
bool cmp(conflict r1,conflict r2)
{
return(r1.c>r2.c);
}
void solve()
{
cin>>n>>m;
init();//初始化
for(int i=1;i<=m;i++)
{
cin>>x[i].a>>x[i].b>>x[i].c;
}
sort(x+1,x+m+1,cmp);//将影响力从大到小排序
for(int i=1;i<=m;i++)
{
if(find(x[i].a)==find(x[i].b))// 冲突不可避免(a、b已经住在一起了)
{
//由于已经将影响力降序排序了,此时冲突产生的影响力即为最大值
cout<< x[i].c<<"\n";
return;
}
//下面讨论冲突可以避免的情况
//分开讨论两个囚犯的情况
//若囚犯a当前没有敌人,那么b就是他的敌人,用数组enemy保存
if(!enemy[x[i].a]) enemy[x[i].a]=x[i].b;
//若囚犯a之前已经存在敌人,那么本着敌人的敌人可以是朋友的原则,我们将a之前的敌人与新敌人b合并(关在一起)
else join(enemy[x[i].a],x[i].b);
//囚犯b的处理同理
if(!enemy[x[i].b]) enemy[x[i].b]=x[i].a;
else join(enemy[x[i].b],x[i].a);
}
//若循环结束,说明冲突均可避免
cout<<"0"<<"\n";
return;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
// cin>>t;
t=1;
while(t--)
{
solve();
}
return 0;
}