【温州中学】好朋友

题目链接（咕咕咕？）

好朋友

题目描述

　　noip2011就要来了，W校的同学们不仅看重这次比赛，更看重noip2011和谁住在同一个房间。同学之间的关系好坏可以用一个亲密值表示，亲密值越大，两个同学关系越好。小A作为W校信息组的组长，自然想要让同学们在比赛前能好好休息，放松心情，让同学们在赛场上能够超常发挥。他现在知道自己预订的房间都是双人间，且知道这\(n\)个同学之间的关系。\(n\)个同学的关系可以用一个\(n\)条双向边的连通图来描述，即某个同学只愿意和与他有边相连的同学住同一个房间，边权即为两个同学的亲密值。数据保证没有重边、自环。现在小A想知道在让所有同学的要求满足的情况下，亲密值最低的一对同学亲密值最高是多少。

输入格式：

　　第一行一个正整数\(n\)，下面\(n\)行每行三个数\(u\)，\(v\)，\(w\)，表示\(u\)到\(v\)有一条边权为\(w\)的双向边。

输出格式：

　　假如无论如何都无法满足所有同学的要求，输出”no answer”，否则输出亲密值最低的一对同学的最高亲密值。

样例输入：

4
1 2 3
2 3 10
3 4 3
1 4 1

样例输出：

3

数据范围：
50%的数据满足\(n<=20\)；
80%的数据满足\(n<=1000\)；
100%的数据满足\(n<=100000\)，\(-10^9<=w<=10^9\)

时间限制：

1S

空间限制：

64M

提示：

remove!!!

题解

\(n\)个点，\(n\)条边？那不就是一棵树再加上一条边吗？
那么我们只要一直将树（暂且称他为树吧）的叶子节点（也就是度为1）的点所连的那条边删掉（每一个人都要有配对，所以叶子节点的配对方案是惟一的），最后就只剩下那一个环或者环上的一个点被叶子节点删除导致所有节点都被删除。
这里我们可以用宽搜删除节点，删除后更新度为一的节点。
在删除节点的过程中我们要注意无法删除的节点，是否"no answer"。

如上图就得"no answer"。
所以在删除叶子时只要有点没被删除也无法被配对，也就是度为0时，要"no answer"。
接下来考虑环的两种情况就行了。
我们可以用两个变量\(u_1\)，\(u_2\)查找两种情况的最小值。
因为这两个数大于等于之前删叶子时求出的\(ans\)时对\(ans\)没有影响，所以这两个数在搜索前可以等于\(ans\)。
上代码：

#include<bits/stdc++.h>
using namespace std;
int n,ans;
int u,v,w;
struct aa{
    int to,nxt,v;
}p[200009];
int len;
int s[100009];
int pp[100009],l,r;
bool k[100009];
int h[100009];
int u1,u2;
void add(int x,int y,int v){
    len++;
    p[len].to=y;
    p[len].v=v;
    p[len].nxt=h[x];
    h[x]=len;
}
int asdkkk;
bool qq;
void dfs(int x,bool kk){
    k[x]=1;
    for(int j=h[x];j;j=p[j].nxt){
        if(!k[p[j].to] || (p[j].to==asdkkk && qq==0)){
            if(kk) u1=min(u1,p[j].v);
            else u2=min(u2,p[j].v);
            if(qq==1) qq=0;
            if(x==asdkkk) qq=1;
            dfs(p[j].to,!kk);
        }
    }
}
int main(){
    scanf("%d",&n);
    if(n%2){
        printf("no answer");
        return 0;
    }
    for(int j=1;j<=n;j++){
        scanf("%d%d%d",&u,&v,&w);
        ans=max(ans,w);
        add(u,v,w);
        add(v,u,w);
        s[u]++;
        s[v]++;
    }
    for(int j=1;j<=n;j++){
        if(s[j]==1) pp[++r]=j;
        if(s[j]==0){
            printf("no answer");
            return 0;
        }
    }
    while(l<=r){
        int u=0;
        l++;
        if(k[pp[l]]) continue;
        for(int j=h[pp[l]];j;j=p[j].nxt){
            if(!k[p[j].to]){
                u=p[j].to;
                k[pp[l]]=1;
                k[p[j].to]=1;
                ans=min(ans,p[j].v);
                break;
            }
        }
        if(!l){
            printf("no answer");
            return 0;
        }
        for(int j=h[u];j;j=p[j].nxt){
            s[p[j].to]--;
            if(!k[p[j].to]){
                if(s[p[j].to]==1) pp[++r]=p[j].to;
                if(!s[p[j].to]){
                    printf("no answer");
                    return 0;
                }
            }
        }
    }
    for(int j=1;j<=n;j++)
        if(!k[j]){asdkkk=j;break;}
    if(asdkkk){
        u1=u2=ans;
        dfs(asdkkk,1);
        ans=min(ans,max(u1,u2));
    }
    printf("%d",ans);
    return 0;
}

【温州中学】好朋友

原文：https://www.cnblogs.com/linjiale/p/11268404.html