題目大意：

N 道菜肴，1到N的順序編號

某些菜肴必須在另一些菜肴之前制作，具體的，一共有 M 條形如”i 號菜肴'必須'先于 j 號菜肴制作“的限制，我們將這樣的限制簡寫為<i,j>。

(1)在滿足所有限制的前提下，1 號菜肴”盡量“優先制作

(2)在滿足所有限制，1號菜肴”盡量“優先制作的前提下，2號菜肴”盡量“優先制作

(3)在滿足所有限制，1號和2號菜肴”盡量“優先的前提下，3號菜肴”盡量“優先制作

(4)在滿足所有限制，1 號和 2 號和 3 號菜肴”盡量“優先的前提下，4 號菜肴”盡量“優先制作

(5)以此類推

思路：

因為要使小的盡量靠前，所以我們在拓撲排序的時候要加一些處理：

反向建圖，致敬GODV

使圖的字典序最大

然后再反過來輸出，無解的情況為無入度為零的點或跑完一邊答案數量小于n

1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cmath> 5 #include<cstring> 6 #include<cstdlib> 7 #include<set> 8 #include<map> 9 #include<vector> 10 #include<stack> 11 #include<queue> 12 #define ll long long 13 #define inf 2147383611 14 #define MAXN 100100 15 using namespace std; 16 inline int read() 17 { 18 int x=0,f=1; 19 char ch;ch=getchar(); 20 while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();} 21 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();} 22 return x*f; 23 } 24 int n,m,next[MAXN*2],first[MAXN],to[MAXN*2],ind[MAXN]; 25 int cnt,rank[MAXN]; 26 void add(int u,int v) {next[++cnt]=first[u],first[u]=cnt,to[cnt]=v,ind[v]++;} 27 priority_queue <int> q; 28 int main() 29 { 30 int T; 31 T=read(); 32 while(T--) 33 { 34 cnt=0; 35 memset(first,0,sizeof(first)); 36 memset(next,0,sizeof(next)); 37 memset(ind,0,sizeof(ind)); 38 memset(to,0,sizeof(to)); 39 n=read(),m=read(); 40 int a,b; 41 while(m--) {a=read(),b=read();add(b,a);} 42 for(int i=1;i<=n;i++) if(!ind[i]) q.push(i); 43 cnt=0; 44 if(q.empty()) {printf("Impossible!\n");continue;} 45 while(!q.empty()) 46 { 47 int k=q.top();q.pop(); 48 for(int i=first[k];i;i=next[i]) 49 { 50 ind[to[i]]--; 51 if(!ind[to[i]]) q.push(to[i]); 52 } 53 rank[++cnt]=k; 54 } 55 if(cnt!=n) {printf("Impossible!\n");while(!q.empty()) q.pop();continue;} 56 for(int i=cnt;i>=1;i--) printf("%d ",rank[i]); 57 printf("\n"); 58 } 59 } View Code

轉載于:https://www.cnblogs.com/yyc-jack-0920/p/7756373.html

總結

以上是生活随笔為你收集整理的bzoj 4010 菜肴制作的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。