XJOI夏令营501-511NOIP训练14——好朋友

快来打我* 2021-11-01 13:24 261阅读 0赞

传送门：[QAQQAQ][]

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

思路：比赛的时候居然没想出来，打了个暴力只有30分。。。（这场比赛打炸了说）

这道题第一反应是二分，事实上只要$O(n)$贪心即可。

因为有$n$个点$n$条边，而且是个连通图，所以它是一个基环树（只有一个环），我们考虑只是一个树的情况：枚举每一个叶子结点，然后因为它们的度为1，所以只能和它们的父亲相连，然后和拓扑排序一样删边，遇到有点不能匹配或者有点匹配两次，就$No Answer$

我们就这样“拓扑排序”，剩下来没有搜到的点一定在一个环里而且这个环没有被破坏（这里需要人工YY一下），那么我们就可以对这个环进行染色，然后分两种情况求最小值即可。

代码：（强调！vector的size一定要转为int！）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int N=200001;
    const int inf=(int)2e9;
     
    struct Edge{
        int to,w;
        Edge(){}
        Edge(int to,int w) : to(to),w(w){}
    };
    vector<Edge> E[N];
    vector<Edge> R; int F;
    int n,ans=inf;
     
    int f,vis[N];
    int deg[N],bl[N];
    queue<int> q;
    void dfs(int u,int f)
    {
        vis[u]=1;
        for(int i=0;i<(int)E[u].size();i++)
        {
            int v=E[u][i].to;
            if(v==f||bl[v]) continue;
            R.push_back(E[u][i]);
            if(!vis[v]) dfs(v,u);
            break;
        }
    }
     
    int main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            int x,y,W;
            scanf("%d%d%d",&x,&y,&W);
            E[x].push_back(Edge(y,W));
            E[y].push_back(Edge(x,W));
            deg[x]++; deg[y]++;
        }
        for(int i=1;i<=n;i++)
            if(deg[i]==1) q.push(i);
        int sum=0;
        while(!q.empty())
        {
            int u=q.front(),v=-1; q.pop();
            if(bl[u]) continue;
            bl[u]=1;
            for(int i=0;i<E[u].size();i++)
            {
                int now=E[u][i].to;//之前直接赋值为v,就算不成立下面也不会判
                if(bl[now]) continue;
                v=now;
                ans=min(ans,E[u][i].w);
                break;
            }
            if(v==-1)
            {
                puts("no answer");
                return 0;
            }
            bl[v]=1; sum+=2;
            for(int i=0;i<(int)E[v].size();i++)
            {
                int p=E[v][i].to;
                if(bl[p]) continue;
                deg[p]--; if(deg[p]==1) q.push(p);
            }
        }
        if(sum==n)
        {
            cout<<ans<<endl;
            return 0;
        }
        for(int i=1;i<=n;i++) if(!bl[i]) F=i;
        dfs(F,-1);
        if((int)R.size()%2==1)
        {
            puts("no answer");
            return 0;
        }
        int now1=inf,now2=inf;
        for(int i=0;i<(int)R.size();i++)
        {
            if(i%2==0) now1=min(now1,R[i].w);//之前min写成加了
            else now2=min(now2,R[i].w);
        }
        ans=min(ans,max(now1,now2));
        cout<<ans<<endl;
        return 0;
    }

转载于:https://www.cnblogs.com/Forever-666/p/11265765.html

[QAQQAQ]: https://dev.xjoi.net/contest/1210/problem/2
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/3d47b236a47e4a40a2d6fb2905bde616.png