题解 P1160 【队列安排】

· · 题解

第一篇题解，啊，蒟蒻的我无比激动；

------------咳咳------------

说实话，写这道题是因为我们老师明天要考该类型，然后临时抱佛脚。。。

------------咳咳------------

好了说正事，这个是一个链式结构，确实也是线性，我们大家可以想象一下一个链子，一块一块连起来，是头挨头尾接尾 （这个说法好zz）

反正大家想象一下就好（我的物理老师告诉我做题都是要情景想象）

好的，大家都想象好了，然后我们就引进两个数组head[]，next[]; 顾名思义，它就是头和尾的意思。思考一下，怎么连接呢？

大家可以查一下有一个叫 前向星 和 链式前向星 （ssfz神牛Malash最强），重点就是链式前向星，大家一定要看。

然后就有了这个

if(!p){ //放在左边 
            next[head[k]]=i;//断开链子并接上 
            head[i]=head[k];//将我们上一步完善 
            next[i]=k;// 连接下一个 
            head[k]=i;//将下一个的head连在i上 
        }else{//放在右边，而且具有对称性，比较容易来修改代码 
            head[next[k]]=i;
            next[i]=next[k];
            head[i]=k;
            next[k]=i;//由于同理，就不再解释了 
        }

大家可以手动模拟一下咯，受到链式前向星的启发就有了它；

    0   1   2   3   4

head / 4 0 2 3 next 2 0 3 4 1

作为一个良心讲题人，上面是我模拟的（有错请指出，我没在纸上写）

再模拟几遍大家就应该知道了；

删去了话，其实也可以用链式的常规操作，但是我太懒，而数据又不是太大，所以开了个桶，操作简单。

再附上蒟蒻的代码

#include<bits/stdc++.h>//万能头 大家都在用吧 
using namespace std;
int n,tong[100007],m;//桶删数 
int head[100007],next[100007];//链式常规操作 
int main(){
    scanf("%d",&n);
    next[0]=1;//将0的下一个定为1 
    for(int i=2,p,k;i<=n;i++){
        scanf("%d%d",&k,&p);
        if(!p){ //放在左边 
            next[head[k]]=i;//断开链子并接上 
            head[i]=head[k];//将我们上一步完善 
            next[i]=k;// 连接下一个 
            head[k]=i;//将下一个的head连在i上 
        }else{//放在右边，而且具有对称性，比较容易来修改代码 
            head[next[k]]=i;
            next[i]=next[k];
            head[i]=k;
            next[k]=i;//由于同理，就不再解释了 
        }
    }
    scanf("%d",&m);
    for(int i=1,t;i<=m;i++){
        scanf("%d",&t);
        tong[t]=1;//tong删法 
    }
    for(int i=next[0];1;i=next[i]){
        if(!tong[i]) printf("%d ",i);
        if(!next[i]) break;/*为甚要放在后面而不是for循环上，
        大家可以试试，这样应该就能明白了 */
    }
}

（呼，第一篇题解，好虚好虚）

这样大家就可以了解链式结构了 最后附上链式前向星，（板子可能不好，仅供参考）

void add(int a,int b,int w){
    edge[++cent].next=head[a];
    edge[cent].to=b;
    edge[cent].w=w;
    head[a]=cent;
}

有什么错误，请各位大佬指出，我会第一时间改的(｀・ω・´)