Milking Order(拓扑排序+二分+优先队列)
程序员文章站
2022-06-07 15:15:59
...
题意:
这个中文还是有一些罗嗦,还是自己手写一下题意吧,题目说农夫John有N头牛,然后他有一天发现,m种规律,他说这个顺序,如果按照这个顺序挤奶,会使得利益增大,然后满足某一条规律如 第 x 条规律,一定要满足前x-1条规律。农夫想要最大化这个X的值。
题解:
1、为什么要涉及拓扑排序呢?
2、为什么要涉及二分呢?
3、为什么要涉及优先队列呢?
一、为什么涉及拓扑排序:
-
其实认真思考一下,其实只考虑符合一条规律好简单,但是要同时符合多条规律不容易。
-
因为有不合法的情况。
如示例:
大家看,如果出现曲线部分就是不合法。光是满足前两条规律就够呛了。
如果出现曲线部分,肯定是成环了,其实只要不成环肯定有一个序列满足多条规律的。
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;
}
上一篇: CCF201903-2 二十四点(100分)(Java)
下一篇: X - 拓扑排序·一