备战蓝桥杯---搜索（完结篇）

再看一道不完全是搜索的题：

解法1：贪心+并查集：

把冲突事件从大到小排，判断是否两个在同一集合，在的话就返回，不在的话就合并。

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,c;
struct node{int x,y,qi;
}a1[100010];
int fa[50000];
bool cmp(node a,node b){return a.qi>b.qi;
}
int find(int x){if(fa[x]==x) return x;else return fa[x]=find(fa[x]);
}
void merge(int x,int y){fa[find(x)]=find(y);
}
int main(){cin>>n>>m;for(int i=1;i<=m;i++){scanf("%d%d%d",&a1[i].x,&a1[i].y,&a1[i].qi);}for(int i=1;i<=2*n+1;i++){fa[i]=i;}sort(a1+1,a1+1+m,cmp);int f=0;for(int i=1;i<=m;i++){int xx=a1[i].x;int yy=a1[i].y;if(find(xx)==find(yy)){cout<<a1[i].qi;f=1;break;}else{merge(xx,n+yy);merge(xx+n,yy);}}if(f==0) cout<<0;
}

解法2：二分+DFS

显然这是一个0/1单调函数，我们可以进行二分。那我们二分出值如何判断是否可行？

我们可以把有怨气值的连边，对每个联通块种的大于二分值的DFS，先把自己-》1，与他相连的赋为0，以此类推，看是否有两个0/1值相同并相连的节点。

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,a,b,c,qi;
struct node{int aa,qi1;
};
vector<node> tu[20005];
int vis[20005];
int heibai[20005];
int dfs(int x,int fa,int mid){int f=0;vis[x]=1;heibai[x]=1-heibai[fa];for(int i=0;i<tu[x].size();i++){if(tu[x][i].qi1<=mid) continue;if(tu[x][i].aa==fa) continue;if(vis[tu[x][i].aa]==1&&heibai[tu[x][i].aa]==heibai[x]){f=1;continue;}if(vis[tu[x][i].aa]==1) continue;if(dfs(tu[x][i].aa,x,mid)==1) f=1;}
return f;
}
int check(int mid){memset(vis,0,sizeof(vis));memset(heibai,0,sizeof(heibai));int f=1;for(int i=1;i<=n;i++){if(vis[i]==1) continue;if(dfs(i,0,mid)==1){f=0;break;}}return f;
}
signed main(){cin>>n>>m;for(int i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&c);tu[a].push_back({b,c});tu[b].push_back({a,c});qi=max(qi,c);}int i=0,j=qi;while(i<j){int mid=(i+j)/2;if(check(mid)==1) j=mid;else i=mid+1;}cout<<i;
}