题目大意：求编号位置序最小(每个编号所在位置最小)
方法1：
建链表，每次把需要放在他前面的放前面，递归去找，最后的表应该就是答案，但是他好像是错的
30·
1 #include<cstdio> 2 #include<cstring> 3 #include<cstdlib> 4 #include<algorithm> 5 #include<iostream> 6 #include<cmath> 7 #include<queue> 8 using namespace std; 9 const int maxn=1e5+5; 10 int n,m,T; 11 int fst[maxn],nxt[maxn],to[maxn],edge_count,indegree[maxn]; 12 inline void add(int x,int y){ 13 edge_count++; 14 to[edge_count]=y; 15 nxt[edge_count]=fst[x]; 16 fst[x]=edge_count; 17 indegree[y]++; 18 } 19 bool vis[maxn]; 20 queue<int>q; 21 int cnt; 22 inline bool topological_sort(){ 23 cnt=0; 24 for(int i=1;i<=n;i++)if(!indegree[i])q.push(i),cnt++; 25 while(q.size()){ 26 int u=q.front(); 27 q.pop(); 28 29 for(int i=fst[u];i;i=nxt[i]){ 30 int v=to[i]; 31 indegree[v]--; 32 if(!indegree[v])q.push(v),cnt++; 33 } 34 } 35 return cnt==n; 36 } 37 int pre[maxn],suf[maxn]; 38 inline void ins(int x,int p){//在p( 数值 )前插入x 39 int l=pre[p]; 40 pre[x]=l; 41 suf[l]=x; 42 43 pre[p]=x; 44 suf[x]=p; 45 46 vis[x]=1; 47 } 48 inline void del(int x){//将x从链表中删除 49 int l=pre[x]; 50 int r=suf[x]; 51 suf[l]=r; 52 pre[r]=l; 53 } 54 inline void init(){ 55 for(int i=0;i<=n+1;i++){ 56 pre[i]=i-1; 57 suf[i]=i+1; 58 } 59 } 60 int flag[maxn]; 61 int temp[maxn],p; 62 inline void solve(int x,int y){//传数值 63 int dep=++cnt; 64 for(int k=x;pre[k]!=y;k=suf[k])flag[k]=dep; 65 66 for(int k=x;flag[k]==dep;k=suf[k]){ 67 p=0; 68 vis[k]=1; 69 70 for(int i=fst[k];i;i=nxt[i]){ 71 int v=to[i]; 72 if(!vis[v])temp[++p]=v; 73 } 74 if(p){ 75 sort(temp+1,temp+p+1); 76 for(int i=1;i<=p;i++){ 77 del(temp[i]); 78 ins(temp[i],k); 79 } 80 solve(temp[1],temp[p]); 81 } 82 } 83 if(x==1 && y==n){ 84 for(int k=1,ans=1;ans<=n;k=suf[k],ans++){ 85 printf("%d ",k); 86 } 87 printf("\n"); 88 } 89 } 90 inline void clear(){ 91 memset(indegree,0,sizeof(indegree)); 92 memset(fst,0,sizeof(fst)); 93 memset(nxt,0,sizeof(nxt)); 94 memset(to,0,sizeof(to)); 95 edge_count=0; 96 memset(vis,0,sizeof(vis));//标记是否处理过 97 memset(pre,0,sizeof(pre)); 98 memset(suf,0,sizeof(suf)); 99 init(); 100 } 101 int main(){ 102 103 scanf("%d",&T); 104 while(T--){ 105 106 scanf("%d%d",&n,&m); 107 clear(); 108 for(int i=1,a,b;i<=m;i++){ 109 scanf("%d%d",&a,&b); 110 add(b,a);//b前面有a 111 } 112 if(!topological_sort()){printf("impossible\n");continue;} 113 else cnt=0,solve(1,n); 114 } 115 return 0; 116 }
希望dalao们想出反例...
。。。艹。。。rechardluan竟然在几分钟之内就想到反例了
我的算法是基于保证比x小的节点都在x前面，但是问题就在于 每次处理的序列并不一定符合题目要求(不完全等价)，比如一组数据是
5 3
5 2
4 2
3 5
12345 -> 1 45 23 -> 14 3 52
但是正确答案应该是
13452
正解:
一个数的位置确定，当且仅当比这个数大的 以及 必须在他后面的 都在他后面(不能把 比他小的放前面,会有问题)
所以我们会想到建反图，每次找最大的 零度节点 删除
最后倒序输出就是答案，完美的避开了之前说的递归区间会有的问题
std：
1 #include<cstdio> 2 #include<cstring> 3 #include<cstdlib> 4 #include<algorithm> 5 #include<iostream> 6 #include<cmath> 7 #include<queue> 8 using namespace std; 9 const int maxn=1e5+5; 10 int n,m,T; 11 int fst[maxn],nxt[maxn],to[maxn],edge_count,indegree[maxn]; 12 inline void add(int x,int y){ 13 edge_count++; 14 to[edge_count]=y; 15 nxt[edge_count]=fst[x]; 16 fst[x]=edge_count; 17 indegree[y]++; 18 } 19 bool vis[maxn]; 20 priority_queue<int>q; 21 int ans[maxn]; 22 int cnt; 23 inline bool topological_sort(){ 24 cnt=0; 25 for(int i=1;i<=n;i++)if(!indegree[i]){ 26 q.push(i); 27 } 28 while(q.size()){ 29 int u=q.top(); 30 ans[++cnt]=u; 31 q.pop(); 32 33 for(int i=fst[u];i;i=nxt[i]){ 34 int v=to[i]; 35 indegree[v]--; 36 if(!indegree[v])q.push(v); 37 } 38 } 39 return cnt==n; 40 } 41 inline void clear(){ 42 memset(indegree,0,sizeof(indegree)); 43 memset(fst,0,sizeof(fst)); 44 memset(nxt,0,sizeof(nxt)); 45 memset(to,0,sizeof(to)); 46 edge_count=0; 47 } 48 int main(){ 49 scanf("%d",&T); 50 while(T--){ 51 scanf("%d%d",&n,&m); 52 clear(); 53 for(int i=1,a,b;i<=m;i++){ 54 scanf("%d%d",&a,&b); 55 add(b,a);//b前面有a 56 } 57 if(!topological_sort()){printf("impossible\n");continue;} 58 else{ 59 for(int i=n;i;i--){ 60 printf("%d ",ans[i]); 61 } 62 printf("\n"); 63 } 64 } 65 return 0; 66 }
总结:
1.证明算法的复杂度。2.证明算法的正确性(往往贪心算法都需要想反例，从算法的 每一步 去思考，想出可能会造成问题的环节)
原文：https://www.cnblogs.com/a-blog-of-taojiayi-2003/p/11536484.html
