题解 | #工厂流水线#

读题

且保证上一步的组件只会被下一步中一个零件引用

只有一个零件所需的全部组件的上一步工序完成，才能进行下一步工序

每台机器同时开始加工，流水线严格按照时序进行，不存在等待情况

这句话说明了Yes或No的判断标准，这可能不是很好理解，所以我们又要回到示例图，根据示例图，可以发现，机器是按从先到后的顺序去执行自己的加工命令的。比如说第一个示例的第一台机器，

1. 花1小时生产1号零件
2. 花3小时生产2号零件
3. 花5小时用4号零件生产3号零件。

综上可以发现，只要关心每次都有足够的零件执行工序即可，剩余多少零件与流水线正常运行与否没有关系。

解题

把每台机器看作是一个队列。同时模拟时间的运行。每过1小时，就把所有机器队列头的时间减一，弹出时间为0的工序，并在此时进行判定。

用链表维护机器， 用队列维护机器内的工序 工序(struct)用结果(int)和原料(vector)表示

代码

struct process{
    int product;
    int time;
    vector<int> raw;
};

bool isright(list<queue<process>>&machines,set<int>&have){
    list<queue<process>>::iterator nowp=machines.begin();
        
    while(nowp!=machines.end()){
        if(nowp->front().raw.size()!=0){
            return false;
        }
        ++nowp;
    }
    while(!machines.empty()){
        nowp=machines.begin();
        for(;nowp!=machines.end();++nowp){
            if(--(nowp->front().time)==0){
  //对所有时间流逝 以及 收获阶段
                have.insert(nowp->front().product);
            }
        }//先结算所有完成的零件
        
        nowp=machines.begin();
        while(nowp!=machines.end()){
            if(nowp->front().time==0){
                nowp->pop();//删除旧的
                if(!nowp->empty()){
                    if(nowp->front().raw.size()!=0){//投入原料阶段
                        for(int rawNO:nowp->front().raw){//遍历所有原料
                            if(have.find(rawNO)!=have.end()){
                                have.erase(rawNO);
                            }else{
                                return false;
                            }
                        }
                    }
                    ++nowp;
                }else{
                    nowp=machines.erase(nowp);
                }
            }else{
                ++nowp;
            }
        }
        
    }
    return true;
}

//Extern vars are above
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif // LOCAL   
    int T;
    cin>>T;
    while(T--){
        int n,m;
        cin>>n;
        set<int> have;
        list<queue<process>> machines;
        while(n--){
            cin>>m;
            machines.push_front(queue<process>());//不同机器间的顺序不重要
            list<queue<process>>::iterator nowp=machines.begin();
            
            int product,time,n_raw;
            while(m--){
                cin>>product>>time>>n_raw;
                nowp->push({});
                nowp->back().product=product;
                nowp->back().time=time;
                if(n_raw!=0){
                    int tem;
                    while(n_raw--){
                        cin>>tem;
                        nowp->back().raw.push_back(tem);
                    }
                }
            }
        }
        if(isright(machines,have)){
            cout<<"Yes\n";
        }else{
            cout<<"No\n";
        }
    }
    
}