题解：CF1423B Valuable Paper

· · 题解

CF1423B 题解

题解貌似都是网络流和 Dinic 的方法，对于一个蒟蒻这些还是太难了，所以我用了一种新奇的方法。

小题面

给你两个大小为 n 的点集，在 m 条边中选 n 条边，使得每个点连且仅连一条边，问选取的边中边权最大值最小是多少，如无解，输出 -1。

小方法

首先如果我们可以很容易看出本体符合单调性，即可用二分答案加 check 去找到答案。

而若当前二分到的边权为 w，那么边权小于等于 w 的边都能进入候选集合，为此我们可以将边按边权进行排序。

check 时，可以想到直接进行建图。因每个连通块间互不影响，可以将连通块分开考虑。在每个连通块中，若其中开始就给定的两个集合中的存在在该连通块中的节点个数不同，则必定无法满足题目要求，这部分可以用并查集进行实现。（后面步骤均基于这条）

如果该连通块本身就为包含一个环（由所有节点组成），可以邻点成对连接即可。若本身不是一个环，那么必定存在连边仅为 1 的点，而仅连一条边的点的选取方案是一定的，所以我们每次将选取方案确定的点按方案取出，进行一个删边删点操作，若一点唯一搭配的点已被其他选过则必定无解。所有操作结束后，剩下的必定是个环，而必定有解。

那么本题便简单的做完了。

小代码

#include<bits/stdc++.h>//码风不好，请见谅
using namespace std;
#define endl '\n'
#define ll long long
const int N=2e5+10;
struct EDGE
{
    int x,y,d;
}edge[N];
int book[N],du[N],n,m,fa[N],s[N],t[N];
bool cmp(EDGE a,EDGE b)
{
    return a.d<b.d;
}
int find(int x)
{
    if(fa[x]==x)return x;
    else return fa[x]=find(fa[x]);
}
vector<int>v[N];
bool check(int f)
{
    for(int i=1;i<=(n<<1);i++)//初始化+清空
    {
        s[i]=t[i]=0;
        book[i]=0;
        fa[i]=i;
        v[i].clear();
    }
    for(int i=1;i<=f;i++)//建图
    {
        v[edge[i].x].push_back(edge[i].y+n);
        v[edge[i].y+n].push_back(edge[i].x);
        fa[find(edge[i].x)]=find(edge[i].y+n);//并查集
    }
    queue<int>q;
    for(int i=1;i<=n;i++)//为下面的删边初始化
    {
        if(v[i].size()==1)
        {
            q.push(i);
        }
        if(v[i+n].size()==1)
        {
            q.push(i+n);
        }
        du[i]=v[i].size();
        du[i+n]=v[i+n].size();
    }
    while(!q.empty())//删边
    {
        int u=q.front(),k=0;
        q.pop();
        if(book[u])continue;
        for(int i=0;i<v[u].size();i++)
        {
            int vv=v[u][i];
            if(!book[vv])
            {
                du[vv]--;
                k=vv;
                break;
            }
        }
        if(!k)continue;
        book[u]=1;
        book[k]=1;
        u=k;
        for(int i=0;i<v[u].size();i++)
        {
            int vv=v[u][i];
            du[vv]--;
            if(du[vv]==1)
            {
                q.push(vv);
            }
        }
    }
    for(int i=1;i<=(n<<1);i++)
    {
        if(!(book[i]|du[i]))
        {
            return 0;
        }
    }
    for(int i=1;i<=n;i++)
    {
        s[find(i)]++;
    }
    for(int i=1+n;i<=n+n;i++)
    {
        t[find(i)]++;
    }
    for(int i=1;i<=(n<<1);i++)
    {
        if(s[i]!=t[i])return 0;
    }
    return 1;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);cout.tie(NULL);
    cin>>n>>m;
    for(int i=1;i<=m;i++)cin>>edge[i].x>>edge[i].y>>edge[i].d;
    sort(edge+1,edge+m+1,cmp);//排序
    int l=1,r=m,ans=-1;//二分
    while(l<=r)
    {
        int mid=l+r>>1;
        if(check(mid))
        {
            r=mid-1;
            ans=edge[mid].d;
        }
        else l=mid+1;
    }
    cout<<ans;
    return 0;
}

希望看完本篇题解才A的人给个赞，谢谢