noi.ac #535 生成树

题目链接：戳我


我们考虑按照编号依次加点，然后维护一个栈。
预设生成树的颜色为color。
对于当前点x，如果它和栈首的点连边颜色相同，那么他们的连边可以作为生成树上面的边，点i已经连接，直接break掉即可。
如果和栈首的点连边颜色和预设颜色不同，那么这条边是不能连的，弹栈。但是前面的点已经构成了生成树，所以我们看一看能不能和前面栈里的点连起来，如果可以的话，自然是把这个边放到生成树的边里就星了。如果一直弹到栈空都没有找到的话，相当于这个点可以和前面的所有点都连上另外一种颜色的边，我们直接把颜色翻转一下就可以了qwq。

#include
#include
#include
#include
#include
#include
#include
#include
#define MAXN 500010
#define ll long long
#define mp make_pair
using namespace std;
int n,m;
ll X,Y,Z,P[MAXN];
mapc[MAXN];
inline int query(int x,int y)
{
    if(c[x].count(y)) return c[x][y];
    if((X*min(x,y)+Y*max(x,y))%Z >g[2];
    stackq;
    q.push(1);
    int color=0;
    for(int i=2;i<=n;i++)
    {
        while(!q.empty())
        {
            int x=q.top();
            int c=query(x,i);
            g[c].push_back(mp(x,i));
            if(c!=color) q.pop();
            else break;
        }
        if(q.empty()) color^=1,q.push(1);
        q.push(i);
    }
    if(g[color].size()!=n-1) printf("No solution");
    else
    {
        for(int i=0;i
图论——生成树其他——构造

相关

标签