欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Milking Order(拓扑排序+二分+优先队列)

程序员文章站 2022-06-07 15:15:59
...

传送门

题意:

Milking Order(拓扑排序+二分+优先队列)

 这个中文还是有一些罗嗦,还是自己手写一下题意吧,题目说农夫John有N头牛,然后他有一天发现,m种规律,他说这个顺序,如果按照这个顺序挤奶,会使得利益增大,然后满足某一条规律如   第 x 条规律,一定要满足前x-1条规律。农夫想要最大化这个X的值。

题解:

1、为什么要涉及拓扑排序呢?

2、为什么要涉及二分呢?

3、为什么要涉及优先队列呢?

一、为什么涉及拓扑排序:

  • 其实认真思考一下,其实只考虑符合一条规律好简单,但是要同时符合多条规律不容易。

  • 因为有不合法的情况。

如示例:

Milking Order(拓扑排序+二分+优先队列)

大家看,如果出现曲线部分就是不合法。光是满足前两条规律就够呛了。

如果出现曲线部分,肯定是成环了,其实只要不成环肯定有一个序列满足多条规律的。

Milking Order(拓扑排序+二分+优先队列)

2、为什么用二分:

一次复杂度:O(n+e):n个点,e条边。因为每次都要历遍每一个点,而且需要删除起码是e的边,所以复杂度肯定是n+e.

要在m中顺序里查找,复杂度肯定爆炸。m*(n+e)

3、为什么用优先队列:

因为涉及到字典序,当入度=0时,进入队列里面,优先队列可以自动把最小的点放在首位。

 

贴上代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int>mp[N];
vector<int>G[N];
int rd[N];
int n,m,num;
void built(int x){
    int p,q;
    for(int i=1;i<=n;i++){
        mp[i].clear();
        rd[i]=0;
    }
    //memset(rd,0,sizeof(rd));
    for(int i=1;i<=x;i++){
        for(int j=0;j<G[i].size()-1;j++){
            p=G[i][j];
            q=G[i][j+1];
            mp[p].push_back(q);
            rd[q]++;
        }
    }
}
int toposort(){
    int tot=0;
    priority_queue< int ,vector<int> , greater<int> > q;
    for(int i=1;i<=n;i++){
        if(rd[i]==0){
            q.push(i);
        }
    }
    while(!q.empty()){
        int cur=q.top();
        q.pop();
        tot++;
        for(int i=0;i<mp[cur].size();i++){
            int No=mp[cur][i];
            rd[No]--;
            if(rd[No]==0){
                q.push(No);
            }
        }
    }
    if(tot==n){
        return 1;
    }else{
        return 0;
    }
}
void solve(int x){
    built(x);
    int tot=0;
    priority_queue< int ,vector<int> , greater<int> > q;
    for(int i=1;i<=n;i++){
        if(rd[i]==0){
            q.push(i);
        }
    }
    int ans[N];
    while(!q.empty()){
        int cur=q.top();
        q.pop();
        ans[tot++]=cur;
        for(int i=0;i<mp[cur].size();i++){
            int No=mp[cur][i];
            rd[No]--;
            if(rd[No]==0){
                q.push(No);
            }
        }
        printf("%d%c",cur,(q.empty()?'\n':' '));
    }
    /*for(int i=0;i<n;i++){
        printf("%d%c",ans[i],(i==n-1?'\n':' '));
    }*/
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d",&num);
        while(num--){
            int t;
            scanf("%d",&t);
            G[i].push_back(t);
        }
    }
    int l=0,r=m,mid;
    while(l<=r){
        mid=(l+r)>>1;
        built(mid);
        if(toposort()){
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    solve(r);
    return 0;

}

 

相关标签: 拓扑排序