【图论杂题】：G.friends [基环树 / 一般图匹配+二分答案]

题目：

团队链接：friends

题面：

给定一张$n$个点$n$条边的带边权图
要求找到一个边集满足：

• 边集涵盖所有点
• 每个点都通过一条边与另一个点匹配
• 边集中的边边权最小值最大

求边集中边权最小值,若存在，输出点权的最大值，否则输出“no answer”。
范围：$n<=10^6$,保证没有重边和自环

样例：

输入：

6
6 3 2
4 6 2
2 1 9
4 3 1
4 5 6
3 2 -4

输出：

2

题解：

我再次 看到的第一眼，很好的看出来了是二分答案+一般图匹配，想了好长时间才发现是基环树，那就比较好写了，可以仔细观察一下，如果是在一棵树上的话，那就是唯一的最大匹配，那套上一个环之后呢，就不是很一样了，如果环上的点被匹配了，环就会被段成链，那就变成树了；但是如果没有被匹配过，那就绕着环慢慢匹配就行，而且这时候你会发现，只有偶环有解的，最后的ans直接去这两个的max即可。

代码：

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int s=0,w=1; char ch=getchar();while(ch<'0'||ch>'9'){
    if(ch=='-')w=-1;ch=getchar();}while(ch<='9'&&ch>='0') s=s*10+ch-'0',ch=getchar();return s*w;
}
const int ocean=1e9;
const int sea=1e6+7;
struct see{
    int ver,next,edge;}e[sea<<1];
bool flag;
int n,cnt,tot,tail,ans,ans1,ans2,d[sea],vis[sea],last[sea<<1],Q[sea];
void add(int x,int y,int z){
    ++d[x];e[++tot].edge=z;e[tot].ver=y;e[tot].next=last[x];last[x]=tot;}
int main()
{
    n=read();ans=ans1=ans2=ocean;for(int i=1;i<=n;i++){
    int x,y,z;x=read(),y=read(),z=read();add(x,y,z); add(y,x,z);}for(int i=1;i<=n;++i) if(d[i]==1) Q[++tail]=i;flag=1;for(int head= 1,u;u=Q[head],head<=tail;++head){
    vis[u]=true;for(int k=last[u], v; v = e[k].ver,k;k = e[k].next){
    if(!vis[v]){
    ans=std::min(ans,e[k].edge);u=v; break;}}vis[u]=true;for(int k=last[u],v;v=e[k].ver,k;k=e[k].next)if(!vis[v]) {
    if(!(--d[v])) flag=0;if(d[v]==1) Q[++tail]=v;}cnt+=2;}if(((n-cnt)&1)||!flag){
     printf("no answer\n");return 0;}int ins=0;for(int i=1;i<=n;i++) if(!vis[i]) ins=i;if(ins){
    for(int v=e[last[ins]].ver;!vis[ins];swap(ans1,ans2))for(int i=last[ins];i;i=e[i].next){
    int y=e[i].ver,z=e[i].edge; if(v!=y){
    vis[ins]=1;ans2=min(ans2,z);y=ins,ins=v;break;}} }printf("%d\n",min(ans,max(ans1,ans2)));return 0;
}

Continue……