头像

xiuzhiyuan

$$\href{https://www.acwing.com/blog/content/14845/}{\Huge\color{blue}{题解主页}}$$




离线:10小时前


最近来访(1807)
用户头像
爱算法爱生活
用户头像
南岸以南南岸哀
用户头像
LIKL
用户头像
acwing_xyy
用户头像
WangJY
用户头像
Acwer
用户头像
面条小王子
用户头像
叔夜
用户头像
Lucky_Xiang
用户头像
菜菜-胶胶
用户头像
云衣醉梦
用户头像
ACWING-XZY
用户头像
罗小呆
用户头像
Hangter
用户头像
zhaokaiyu2012
用户头像
yxc的小迷妹
用户头像
StkOvflow
用户头像
Biu_78
用户头像
有机物
用户头像
爱宣纸

活动打卡代码 AcWing 1100. 抓住那头牛

广搜

#include<iostream>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
int n,k;
bool vis[200010];
inline int bfs(){
    queue<PII> que;
    que.push({n,0});
    while(que.size()){
        int x=que.front().first,step=que.front().second;
        que.pop();
        if(vis[x])
            continue;
        vis[x]=1;
        if(x==k)
            return step;
        if(x>0)
            que.push({x-1,step+1});
        if(x<k)
            que.push({x+1,step+1});
        if(x<k)
            que.push({x<<1,step+1});
    }
}
int main(){
    scanf("%d%d",&n,&k);
    printf("%d",bfs());
    return 0;
}


活动打卡代码 AcWing 4548. 猴子和香蕉

DP

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=190;
struct block{
    int x,y,z;
    bool operator<(const block &W)const{
        if(x!=W.x)
            return x>W.x;
        return y>W.y;
    }
}bs[N];
int f[N];
int main(){
    int n,t=1;
    while(scanf("%d",&n),n){
        for(int i=1;i<=n;i++){
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            bs[i]={x,y,z};
            bs[i+n]={y,x,z};
            bs[i+2*n]={x,z,y};
            bs[i+3*n]={z,x,y};
            bs[i+4*n]={y,z,x};
            bs[i+5*n]={z,y,x};
        }
        sort(bs+1,bs+1+n*6);
        memset(f,0,sizeof f);
        int ans=0;
        for(int i=1;i<=n*6;i++){
            f[i]=bs[i].z;
            for(int j=1;j<i;j++)
                if(bs[i].x<bs[j].x&&bs[i].y<bs[j].y)
                    f[i]=max(f[i],f[j]+bs[i].z);
            ans=max(ans,f[i]);
        }
        printf("Case %d: maximum height = %d\n",t++,ans);
    }
    return 0;
}



题目描述

满足6种操作:

1.插入一个数

2.删除一个数

3.查询一个数的排名

4.查询一个排名对应的值

5.查询一个数的前驱(比它小的最大数)

6.查询一个数的后继(比它大的最小数)

平衡树

平衡树是一种很特殊的二叉树。

每个点有一个权值key

一个点左子树上所有点的权值小于它自己的权值

右子树上所有点的权值大于它自己的权值

所以中序遍历一定是有序的

普通平衡树满足6种操作,也就是题目中的那6种

如果这颗平衡树是完全二叉树,也就是比较平衡的状态,

每次查询平均都是O(logn)的

但是正常插入可能会被卡掉,比如顺次插入5,4,3,2,1

就会变成这样

退化成链.png

这幅图里如果一直查询1,每次查询就是O(n)的,很容易超时

但不难发现,这条链并不是该平衡树的唯一合法形态

一种更平衡的形态就是这样

更平衡的形态.png

所以需要加入另一个权重,var

让它等于一个随机值(rand)

然后优先让var更大的点在上面

这样这棵树虽然不保证一定平衡,但更不容易被卡掉

(出题人:我哪知道这个rand得了个神马东西

总结一下普通平衡树需要存多少信息

struct node{
    int l,r;    //左子树和右子树
    int key,var;    //两个权重
    int cnt,size;   //该key的数目,以及以该点为根的子树的大小(所有cnt相加)
}tr[N];

建树

一开始,我们需要建一棵“空”的平衡树

建两个哨兵

一个编号为1,key为-INF

另一个编号为2,key为INF

哨兵的作用主要有两个

1.方便后续插入,不需要特判第一个插入的点

2.有的题需要自动忽略大于某值或小于某值的数

这时候设置一下INF和-INF的值,如果插入时发现不在合法区域,可以直接忽略

inline void build(){    //建树
    get_node(-INF); //建新点
    get_node(INF);
    root=1;
    tr[1].r=2;  //设置1的右儿子2
    pushup(root);
    if(tr[1].var<tr[2].var) //满足上文所说var大的在上面
        zag(root);
}

由于var的存在,平衡树可能有两种基本形态

基本形态.png

右旋和左旋

为了使树更平衡,需要改变树的形态

接下来考虑如何在不改变中序遍历的情况下改变树的结构

于是右旋(zig)和左旋(zag)就诞生了!

inline void zig(int &p){    //右旋
    int q=tr[p].l;
    tr[p].l=tr[q].r;
    tr[q].r=p;
    p=q;    //通过指针间接改变和原来的p关联的值
    pushup(tr[p].r);
    pushup(p);  //pushup就是更新size
}
inline void zag(int &p){    //左旋
    int q=tr[p].r;
    tr[p].r=tr[q].l;
    tr[q].l=p;
    p=q;    //通过指针间接改变和原来的p关联的值
    pushup(tr[p].l);
    pushup(p);  //更新size
}

画两幅图就会明白

右旋的作用是吧一个点整到原位置的右子树上去

右旋.png

两个形态的中序遍历都是12345

同理,左旋就是右旋的反操作(吧一个点整到原位置的左子树上去)

左旋.png

插入

由递归来实现

设置当前点为p,待插入权值为key

需要分类讨论:

1.p=0(该点不存在)

做法:新建一个点

2.tr[p].key=key(当前点权值与待插入权值相等)

做法:cnt+1

3.tr[p].key>key

做法:递归到左子树

4.tr[p].key<key

做法:递归到右子树

void insert(int &p,int key){
    if(!p)
        p=get_node(key);    //通过指针间接设定l或r
    else if(tr[p].key==key)
        tr[p].cnt++;
    else if(tr[p].key>key){
        insert(tr[p].l,key);
        if(tr[tr[p].l].var>tr[p].var)   //满足var大的在上面
            zig(p);
    }
    else{
        insert(tr[p].r,key);
        if(tr[tr[p].r].var>tr[p].var)   //满足var大的在上面
            zag(p);
    }
    pushup(p);  //维护size
}

删除

如果删除了一个非叶子节点,左子树和右子树会不再连通,是行不通的

(其实也可以吧左子树和右子树重新插入,但代码会更长)

所以只能直接删除叶子节点

如果要删除的是非叶子节点,怎么办呢?

右旋&左旋:你当我们是饭桶?

旋下去就行了!

同理,也是分类讨论,过程省略

void erase(int &p,int key){
    if(!p)  //不存在的话皆大欢喜,直接return
        return;
    if(tr[p].key==key)  //要删除的就在这里
        if(tr[p].cnt>1) //有多个,删一个即可
            tr[p].cnt--;
        else if(tr[p].l||tr[p].r)   //有左子树或右子树
            if(!tr[p].r||tr[tr[p].l].var>tr[tr[p].r].var){  //先删var大的(玄学理论)
                zig(p);
                erase(tr[p].r,key);
            }
            else{
                zag(p);
                erase(tr[p].l,key);
            }
        else    //是叶子节点
            p=0;
    else if(tr[p].key>key)  //递归到下面
        erase(tr[p].l,key);
    else
        erase(tr[p].r,key);
    pushup(p);  //维护size
}

用权值求排名和用排名求权值

也是递归,过程中累加计数,看看就成了

int get_rank_by_key(int p,int key){
    if(!p)  //点不存在
        return 0;
    if(tr[p].key==key)  //
        return tr[tr[p].l].size+1;  //习惯上来讲排名从1开始,要加1
    if(tr[p].key>key)
        return get_rank_by_key(tr[p].l,key);    //左子树的话直接返回就成
    return tr[tr[p].l].size+tr[p].cnt+get_rank_by_key(tr[p].r,key); //右子树的话要累加
}
int get_key_by_rank(int p,int rank){
    if(!p)  //点不存在
        return 0;
    if(tr[tr[p].l].size>=rank)  //在左子树上
        return get_key_by_rank(tr[p].l,rank);
    if(tr[tr[p].l].size+tr[p].cnt>=rank)    //在这个点
        return tr[p].key;
    return get_key_by_rank(tr[p].r,rank-tr[tr[p].l].size-tr[p].cnt);    //右子树要改变排名
}

求前驱和后继

又㕛叒叕是递归,都懒得讲了

int get_prev(int p,int key){
    if(!p)  //前驱不存在
        return -INF;
    if(tr[p].key>=key)  //左子树
        return get_prev(tr[p].l,key);
    return max(tr[p].key,get_prev(tr[p].r,key));    //右子树或本身
}
int get_next(int p,int key){
    if(!p)  //后继不存在
        return INF;
    if(tr[p].key<=key)  //右子树
        return get_next(tr[p].r,key);
    return min(tr[p].key,get_next(tr[p].l,key));    //左子树或本身
}

完整代码

#include<iostream>
using namespace std;
const int N=100010,INF=1e8;
struct node{
    int l,r;
    int key,var;
    int cnt,size;
}tr[N];
int root,idx;
inline void pushup(int p){  //更新大小
    tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+tr[p].cnt;
}
inline int get_node(int key){   //建点
    tr[++idx].key=key;
    tr[idx].var=rand();
    tr[idx].cnt=tr[idx].size=1;
    return idx;
}
inline void zig(int &p){    //右旋
    int q=tr[p].l;
    tr[p].l=tr[q].r;
    tr[q].r=p;
    p=q;
    pushup(tr[p].r);
    pushup(p);
}
inline void zag(int &p){    //左旋
    int q=tr[p].r;
    tr[p].r=tr[q].l;
    tr[q].l=p;
    p=q;
    pushup(tr[p].l);
    pushup(p);
}
inline void build(){    //建树
    get_node(-INF);
    get_node(INF);
    root=1;
    tr[1].r=2;
    pushup(root);
    if(tr[1].var<tr[2].var)
        zag(root);
}
void insert(int &p,int key){
    if(!p)
        p=get_node(key);    //通过指针间接设定l或r
    else if(tr[p].key==key)
        tr[p].cnt++;
    else if(tr[p].key>key){
        insert(tr[p].l,key);
        if(tr[tr[p].l].var>tr[p].var)
            zig(p);
    }
    else{
        insert(tr[p].r,key);
        if(tr[tr[p].r].var>tr[p].var)
            zag(p);
    }
    pushup(p);
}
void erase(int &p,int key){
    if(!p)
        return;
    if(tr[p].key==key)
        if(tr[p].cnt>1)
            tr[p].cnt--;
        else if(tr[p].l||tr[p].r)
            if(!tr[p].r||tr[tr[p].l].var>tr[tr[p].r].var){
                zig(p);
                erase(tr[p].r,key);
            }
            else{
                zag(p);
                erase(tr[p].l,key);
            }
        else
            p=0;
    else if(tr[p].key>key)
        erase(tr[p].l,key);
    else
        erase(tr[p].r,key);
    pushup(p);
}
int get_rank_by_key(int p,int key){
    if(!p)  //点不存在
        return 0;
    if(tr[p].key==key)
        return tr[tr[p].l].size+1;
    if(tr[p].key>key)
        return get_rank_by_key(tr[p].l,key);
    return tr[tr[p].l].size+tr[p].cnt+get_rank_by_key(tr[p].r,key);
}
int get_key_by_rank(int p,int rank){
    if(!p)  //点不存在
        return 0;
    if(tr[tr[p].l].size>=rank)
        return get_key_by_rank(tr[p].l,rank);
    if(tr[tr[p].l].size+tr[p].cnt>=rank)
        return tr[p].key;
    return get_key_by_rank(tr[p].r,rank-tr[tr[p].l].size-tr[p].cnt);
}
int get_prev(int p,int key){
    if(!p)
        return -INF;
    if(tr[p].key>=key)
        return get_prev(tr[p].l,key);
    return max(tr[p].key,get_prev(tr[p].r,key));
}
int get_next(int p,int key){
    if(!p)
        return INF;
    if(tr[p].key<=key)
        return get_next(tr[p].r,key);
    return min(tr[p].key,get_next(tr[p].l,key));
}
int main(){
    build();
    int n;
    scanf("%d",&n);
    while(n--){
        int type,x;
        scanf("%d%d",&type,&x);
        if(type==1)
            insert(root,x);
        else if(type==2)
            erase(root,x);
        else if(type==3)    //从0开始,要-1
            printf("%d\n",get_rank_by_key(root,x)-1);
        else if(type==4)
            printf("%d\n",get_key_by_rank(root,x+1));
        else if(type==5)
            printf("%d\n",get_prev(root,x));
        else
            printf("%d\n",get_next(root,x));
    }
    return 0;
}


活动打卡代码 AcWing 265. 营业额统计

平衡树

#include<iostream>
using namespace std;
typedef long long LL;
const int N=32777,INF=1e7;
struct node{
    int l,r;
    int key,var;
}tr[N];
int root,idx;
inline int get_node(int key){
    tr[++idx].var=rand();
    tr[idx].key=key;
    return idx;
}
inline void zig(int &p){
    int q=tr[p].l;
    tr[p].l=tr[q].r;
    tr[q].r=p;
    p=q;    //通过指针改变当前根节点
}
inline void zag(int &p){
    int q=tr[p].r;
    tr[p].r=tr[q].l;
    tr[q].l=p;
    p=q;
}
inline void build(){
    get_node(-INF);
    get_node(INF);
    root=1;
    tr[1].r=2;
    if(tr[1].var<tr[2].var)
        zag(root);
}
void insert(int &p,int key){
    if(!p)
        p=get_node(key);    //通过指针间接设定l或r
    else if(tr[p].key==key)
        return;
    else if(tr[p].key>key){
        insert(tr[p].l,key);
        if(tr[tr[p].l].var>tr[p].var)
            zig(p);
    }
    else{
        insert(tr[p].r,key);
        if(tr[tr[p].r].var>tr[p].var)
            zag(p);
    }
}
int get_prev(int p,int key){
    if(!p)
        return -INF;
    if(tr[p].key>key)
        return get_prev(tr[p].l,key);
    return max(tr[p].key,get_prev(tr[p].r,key));
}
int get_next(int p,int key){
    if(!p)
        return INF;
    if(tr[p].key<key)
        return get_next(tr[p].r,key);
    return min(tr[p].key,get_next(tr[p].l,key));
}
int main(){
    build();
    int n;
    scanf("%d",&n);
    LL ans=0;
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        if(i==1)
            ans+=x;
        else
            ans+=min(x-get_prev(root,x),get_next(root,x)-x);
        insert(root,x);
    }
    printf("%lld",ans);
    return 0;
}


活动打卡代码 AcWing 253. 普通平衡树

平衡树

#include<iostream>
using namespace std;
const int N=100010,INF=1e8;
struct node{
    int l,r;
    int key,var;
    int cnt,size;
}tr[N];
int root,idx;
inline void pushup(int p){  //更新大小
    tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+tr[p].cnt;
}
inline int get_node(int key){   //建点
    tr[++idx].key=key;
    tr[idx].var=rand();
    tr[idx].cnt=tr[idx].size=1;
    return idx;
}
inline void zig(int &p){    //右旋
    int q=tr[p].l;
    tr[p].l=tr[q].r;
    tr[q].r=p;
    p=q;
    pushup(tr[p].r);
    pushup(p);
}
inline void zag(int &p){    //左旋
    int q=tr[p].r;
    tr[p].r=tr[q].l;
    tr[q].l=p;
    p=q;
    pushup(tr[p].l);
    pushup(p);
}
inline void build(){    //建树
    get_node(-INF);
    get_node(INF);
    root=1;
    tr[1].r=2;
    pushup(root);
    if(tr[1].var<tr[2].var)
        zag(root);
}
void insert(int &p,int key){
    if(!p)
        p=get_node(key);    //通过指针间接设定l或r
    else if(tr[p].key==key)
        tr[p].cnt++;
    else if(tr[p].key>key){
        insert(tr[p].l,key);
        if(tr[tr[p].l].var>tr[p].var)
            zig(p);
    }
    else{
        insert(tr[p].r,key);
        if(tr[tr[p].r].var>tr[p].var)
            zag(p);
    }
    pushup(p);
}
void erase(int &p,int key){
    if(!p)
        return;
    if(tr[p].key==key)
        if(tr[p].cnt>1)
            tr[p].cnt--;
        else if(tr[p].l||tr[p].r)
            if(!tr[p].r||tr[tr[p].l].var>tr[tr[p].r].var){
                zig(p);
                erase(tr[p].r,key);
            }
            else{
                zag(p);
                erase(tr[p].l,key);
            }
        else
            p=0;
    else if(tr[p].key>key)
        erase(tr[p].l,key);
    else
        erase(tr[p].r,key);
    pushup(p);
}
int get_rank_by_key(int p,int key){
    if(!p)  //点不存在
        return 0;
    if(tr[p].key==key)
        return tr[tr[p].l].size+1;
    if(tr[p].key>key)
        return get_rank_by_key(tr[p].l,key);
    return tr[tr[p].l].size+tr[p].cnt+get_rank_by_key(tr[p].r,key);
}
int get_key_by_rank(int p,int rank){
    if(!p)  //点不存在
        return 0;
    if(tr[tr[p].l].size>=rank)
        return get_key_by_rank(tr[p].l,rank);
    if(tr[tr[p].l].size+tr[p].cnt>=rank)
        return tr[p].key;
    return get_key_by_rank(tr[p].r,rank-tr[tr[p].l].size-tr[p].cnt);
}
int get_prev(int p,int key){
    if(!p)
        return -INF;
    if(tr[p].key>=key)
        return get_prev(tr[p].l,key);
    return max(tr[p].key,get_prev(tr[p].r,key));
}
int get_next(int p,int key){
    if(!p)
        return INF;
    if(tr[p].key<=key)
        return get_next(tr[p].r,key);
    return min(tr[p].key,get_next(tr[p].l,key));
}
int main(){
    build();
    int n;
    scanf("%d",&n);
    while(n--){
        int type,x;
        scanf("%d%d",&type,&x);
        if(type==1)
            insert(root,x);
        else if(type==2)
            erase(root,x);
        else if(type==3)    //从0开始,要-1
            printf("%d\n",get_rank_by_key(root,x)-1);
        else if(type==4)
            printf("%d\n",get_key_by_rank(root,x+1));
        else if(type==5)
            printf("%d\n",get_prev(root,x));
        else
            printf("%d\n",get_next(root,x));
    }
    return 0;
}


活动打卡代码 AcWing 1277. 维护序列

线段树

#include<iostream>
using namespace std;
const int N=100010;
typedef long long LL;
int n,m,mod;
int a[N];
struct node{
    int l,r,sum;
    int la,lm;
}tr[N<<2];
inline void pushup(int p){
    tr[p].sum=(tr[p<<1].sum+tr[p<<1|1].sum)%mod;
}
inline void pushdown(int p){
    node &root=tr[p],&l=tr[p<<1],&r=tr[p<<1|1];
    l.sum=((LL)l.sum*root.lm+(LL)root.la*(l.r-l.l+1))%mod;
    r.sum=((LL)r.sum*root.lm+(LL)root.la*(r.r-r.l+1))%mod;
    l.la=((LL)l.la*root.lm+root.la)%mod;
    r.la=((LL)r.la*root.lm+root.la)%mod;
    l.lm=(LL)l.lm*root.lm%mod;
    r.lm=(LL)r.lm*root.lm%mod;
    root.la=0;
    root.lm=1;
}
void build(int l,int r,int p){
    tr[p]={l,r,0,0,1};
    if(l==r){
        tr[p].sum=a[l]%mod;
        return;
    }
    int mid=l+r>>1;
    build(l,mid,p<<1);
    build(mid+1,r,p<<1|1);
    pushup(p);
}
void change(int l,int r,int ca,int cm,int p){
    if(l<=tr[p].l&&r>=tr[p].r){
        tr[p].sum=((LL)tr[p].sum*cm+(LL)ca*(tr[p].r-tr[p].l+1))%mod;
        tr[p].la=((LL)tr[p].la*cm+ca)%mod;
        tr[p].lm=(LL)tr[p].lm*cm%mod;
        return;
    }
    pushdown(p);
    int mid=tr[p].l+tr[p].r>>1;
    if(l<=mid)
        change(l,r,ca,cm,p<<1);
    if(r>mid)
        change(l,r,ca,cm,p<<1|1);
    pushup(p);
}
int get(int l,int r,int p){
    if(l<=tr[p].l&&r>=tr[p].r)
        return tr[p].sum;
    pushdown(p);
    int mid=tr[p].l+tr[p].r>>1;
    int res=0;
    if(l<=mid)
        res=get(l,r,p<<1);
    if(r>mid)
        res=(res+get(l,r,p<<1|1))%mod;
    return res;
}
int main(){
    scanf("%d%d",&n,&mod);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    build(1,n,1);
    scanf("%d",&m);
    while(m--){
        int type,l,r,x;
        scanf("%d%d%d",&type,&l,&r);
        if(type==1){
            scanf("%d",&x);
            change(l,r,0,x,1);
        }
        else if(type==2){
            scanf("%d",&x);
            change(l,r,x,1,1);
        }
        else
            printf("%d\n",get(l,r,1));
    }
    return 0;
}



树套树

#include<iostream>
using namespace std;
typedef long long LL;
const int N=500010;
int n,m;
LL a[N],b[N],c[N];
struct node{
    int l,r;
    LL x;
}tr[N<<2];
LL gcd(LL x,LL y){
    if(!y)
        return x;
    return gcd(y,x%y);
}
void build(int l,int r,int p){
    tr[p]={l,r};
    if(l==r){
        tr[p].x=b[l];
        return;
    }
    int mid=l+r>>1;
    build(l,mid,p<<1);
    build(mid+1,r,p<<1|1);
    tr[p].x=gcd(tr[p<<1].x,tr[p<<1|1].x);
}
void change(int p,int x,LL y){
    if(tr[p].l==tr[p].r){
        tr[p].x+=y;
        return;
    }
    int mid=tr[p].l+tr[p].r>>1;
    if(x<=mid)
        change(p<<1,x,y);
    else
        change(p<<1|1,x,y);
    tr[p].x=gcd(tr[p<<1].x,tr[p<<1|1].x);
}
LL get(int l,int r,int p){
    if(l<=tr[p].l&&r>=tr[p].r)
        return tr[p].x;
    LL res=0,mid=tr[p].l+tr[p].r>>1;
    if(l<=mid)
        res=get(l,r,p<<1);
    if(r>mid)
        res=gcd(res,get(l,r,p<<1|1));
    return abs(res);    //差分有可能是负的,要取绝对值
}
inline int lowbit(int x){
    return x&-x;
}
inline void add(int x,LL y){
    for(;x<=n;x+=lowbit(x))
        c[x]+=y;
}
inline LL sum(int x){
    LL res=0;
    for(;x;x-=lowbit(x))
        res+=c[x];
    return res;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        b[i]=a[i]-a[i-1];
    }
    build(1,n,1);
    while(m--){
        char type[2];
        int l,r;
        scanf("%s%d%d",type,&l,&r);
        if(type[0]=='C'){
            LL x;
            scanf("%lld",&x);
            change(1,l,x);
            if(r<n)
                change(1,r+1,-x);
            add(l,x);
            add(r+1,-x);
        }
        else{
            LL ans1=a[l]+sum(l),ans2=l<r?get(l+1,r,1):0;
            printf("%lld\n",gcd(ans1,ans2));
        }
    }
    return 0;
}


活动打卡代码 AcWing 456. 车站分级

拓扑排序

#include<iostream>
#include<cstring>
using namespace std;
const int N=2010,M=1000010;
int n,m;
bool stop[N];
int to[M],ne[M],w[M],h[N],idx=1;
int din[N];
int top[N];
int dist[N];
inline void add(int a,int b,int c){
    to[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++,din[b]++;
}
inline void topsort(){
    int hh=1,tt=1;
    for(int i=1;i<=n+m;i++)
        if(!din[i])
            top[tt++]=i;
    while(hh<tt){
        int x=top[hh++];
        for(int i=h[x];i;i=ne[i]){
            int y=to[i];
            if(--din[y]==0)
                top[tt++]=y;
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        memset(stop,0,sizeof stop);
        int s,from,to;
        scanf("%d",&s);
        for(int i=1;i<=s;i++){
            int x;
            scanf("%d",&x);
            stop[x]=1;
            if(i==1)
                from=x;
            if(i==s)
                to=x;
        }
        int mid=n+i;
        for(int j=from;j<=to;j++)
            if(stop[j])
                add(mid,j,1);
            else
                add(j,mid,0);
    }
    topsort();
    for(int i=1;i<=n;i++)
        dist[i]=1;
    for(int i=1;i<=n+m;i++){
        int x=top[i];
        for(int j=h[x];j;j=ne[j]){
            int y=to[j];
            dist[y]=max(dist[y],dist[x]+w[j]);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
        ans=max(ans,dist[i]);
    printf("%d",ans);
    return 0;
}


活动打卡代码 AcWing 396. 矿场搭建

无向图双联通分量

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef unsigned long long ULL;
const int N=1010;
int to[N],ne[N],h[N],idx;
int low[N],dft[N],nowt;
int s[N],tt;
int root;
bool ic[N]; //记录该点是否为割点
vector<int> bs[N];
int bcnt;
inline void add(int a,int b){
    to[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int x){
    dft[x]=low[x]=++nowt;
    s[++tt]=x;
    if(!h[x]){
        bcnt++;
        bs[bcnt].push_back(x);
        return;
    }
    int cnt=0;
    for(int i=h[x];i;i=ne[i]){
        int y=to[i];
        if(!dft[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
            if(dft[x]<=low[y]){
                cnt++;
                if(x!=root||cnt>1)
                    ic[x]=1;
                ++bcnt;
                do{
                    bs[bcnt].push_back(s[tt]);
                }while(s[tt--]!=y);
                bs[bcnt].push_back(x);
            }
        }
        else
            low[x]=min(low[x],dft[y]);
    }
}
int main(){
    int t=0,m;
    while(scanf("%d",&m),m){
        memset(h,0,sizeof h);
        memset(ic,0,sizeof ic);
        memset(dft,0,sizeof dft);
        for(int i=1;i<=bcnt;i++)
            bs[i].clear();
        idx=1;
        nowt=bcnt=0;
        int n=0;
        while(m--){
            int a,b;
            scanf("%d%d",&a,&b);
            n=max(n,a);
            n=max(n,b);
            add(a,b);
            add(b,a);
        }
        for(root=1;root<=n;root++)
            if(!dft[root])
                tarjan(root);
        int ans1=0; //记录最少出口数
        ULL ans2=1; //记录方案数
        for(int i=1;i<=bcnt;i++){
            int cnt=0,len=bs[i].size();
            for(int j=0;j<len;j++)
                if(ic[bs[i][j]])
                    cnt++;
            if(!cnt)
                if(len>1){
                    ans1+=2;
                    ans2*=len*(len-1)/2;
                }
                else
                    ans1++;
            else if(cnt==1){
                ans1++;
                ans2*=len-1;
            }
        }
        printf("Case %d: %d %llu\n",++t,ans1,ans2);
    }
    return 0;
}



题目描述

有n个矿洞和m条边

需要在若干个矿洞建造出口

满足任意一个矿洞坍塌(无法通过坍塌的矿洞或使用坍塌矿洞的出口)

其他矿洞都能到达至少一个出口


基本思路

首先用tarjan算法把图中所有双联通分量缩成点

无向图双联通分量:任意两点间都有两条或以上的点不重复路径

分块.png

这里要作一个特殊定义:两个割点中间连一条边也算一个块

分块2.png

这样的话就会发现,两个相邻的块一定共同拥有一个割点。

答案1

我们把所有的块分成三类

1.没有割点的块

这种块是孤立的

所以需要在块内两个不同节点上建两个出口

(任意一个塌了可以用另外一个)

还要特判一下:如果只有一个点的话建一个出口就行

2.有一个割点的块

比如上图中红色和绿色的块

这种块要在除割点外任意一点建一个出口

这样如果割点塌了,可以用那个出口

如果出口塌了可以通过割点去到别的块

3.有两个或以上割点的块

比如上图中蓝色和黄色的块

这种块是不需要出口的

不难发现,不管哪个点塌了,都可以通过没塌的割点去到别的块

答案2

还是那三类

1.没有割点的块

如果只包含一个节点的话,相当于ans2×1,是没有任何贡献的

否则可以在任意两个点建立出口

答案乘上 点数×(点数-1)÷2

2.有一个割点的块

在除割点外任意一点建出口

答案乘上 点数-1

3.有两个或以上割点的块

这种块不会建任何出口

所以对答案没有贡献

判断一个点是否为割点

每次tarjan都会有一个遍历的初始节点,记为root

可以把一个割点分为是root和不是root两类

不是root的可以直接判断

if(x!=root&&low[y]>=x)

是root的需要开一个cnt记录一下下面有几个块

只有一个的话有可能是这种情况:

割点.png

这样的点并不是割点

两个及以上才算作割点

割点2.png

if(x==root&&cnt>1)

c++代码实现

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef unsigned long long ULL;
const int N=1010;
int to[N],ne[N],h[N],idx;   //邻接表的那几个数组和变量
int low[N],dft[N],nowt; //tarjan算法的数组和变量
int s[N],tt;    //tarjan算法中的栈
int root;   //当前遍历的起始节点
bool ic[N]; //记录该点是否为割点
vector<int> bs[N];  //存每个块的所有点
int bcnt;   //块数
inline void add(int a,int b){   //邻接表加边
    to[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int x){ //缩点
    dft[x]=low[x]=++nowt;   //打上标记
    s[++tt]=x;  //入栈
    if(!h[x]){  //孤立的点
        bcnt++;
        bs[bcnt].push_back(x);
        return;
    }
    int cnt=0;  //记录下面有几个块
    for(int i=h[x];i;i=ne[i]){
        int y=to[i];
        if(!dft[y]){    //还没遍历过
            tarjan(y);
            low[x]=min(low[x],low[y]);
            if(dft[x]<=low[y]){
                cnt++;
                if(x!=root||cnt>1)
                    ic[x]=1;
                ++bcnt;
                do{ //缩成块
                    bs[bcnt].push_back(s[tt]);
                }while(s[tt--]!=y);
                bs[bcnt].push_back(x);  //x也是块内的点,但不出栈
            }
        }
        else    //遍历过了,是上面的节点
            low[x]=min(low[x],dft[y]);
    }
}
int main(){
    int t=0,m;
    while(scanf("%d",&m),m){
        memset(h,0,sizeof h);
        memset(ic,0,sizeof ic);
        memset(dft,0,sizeof dft);
        for(int i=1;i<=bcnt;i++)
            bs[i].clear();  //初始化数组和vector
        idx=1;
        nowt=bcnt=0;    //初始化变量
        int n=0;
        while(m--){ //加边
            int a,b;
            scanf("%d%d",&a,&b);
            n=max(n,a);
            n=max(n,b); //题目的n要自己算
            add(a,b);
            add(b,a);
        }
        for(root=1;root<=n;root++)  //遍历所有连通块
            if(!dft[root])
                tarjan(root);
        int ans1=0; //记录最少出口数
        ULL ans2=1; //记录方案数
        for(int i=1;i<=bcnt;i++){
            int cnt=0,len=bs[i].size();
            for(int j=0;j<len;j++)  //记录该块中有几个割点
                if(ic[bs[i][j]])
                    cnt++;
            if(!cnt)    //没有割点
                if(len>1){
                    ans1+=2;
                    ans2*=len*(len-1)/2;
                }
                else
                    ans1++;
            else if(cnt==1){    //有一个割点
                ans1++;
                ans2*=len-1;
            }
        }
        printf("Case %d: %d %llu\n",++t,ans1,ans2); //输出答案
    }
    return 0;
}