首页 > 代码库 > hdu2647 Reward 拓扑排序
hdu2647 Reward 拓扑排序
此题的关键在于分层次，最低一层的人的奖金是888，第二层是888+1 ……
分层可以这样实现。建立反向图。在拓扑排序的时候，第一批入度为0的点就处于第一层，第二批处于第二层 ……
由于是逐个遍历入度为0的点，所以怎么实现上面所说的第一批，第二批就需要动点脑。
可以试试下面的测试数据：
4 3
1 3
2 3
4 3
4 3
1 2
2 3
4 3
4 2
1 2
3 4
6 3
1 2
3 4
5 6
测试结果依次是： 3555 3556 3554 5331
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N = 10100, M =20010;struct node{ int to, next;};node edge[M];int ind[N], head[N],que[N],ans[N];int iq,tot,t;void topo(int n){ int i,k,j=0,x,y; t=-1;x=0; for(i=1;i<=n;i++) if(ind[i]==0) que[j++]=i; ans[++t]=j-x; y=0; x=j; for(i=0;i<j;i++) { if(i==ans[t]+y) { ans[++t]=j-x; x=j; y=i; } int u=que[i]; for(k=head[u]; k!=-1; k=edge[k].next) { ind[edge[k].to]--; if(ind[edge[k].to]==0) que[j++]=edge[k].to; } } iq=j;}void addedge(int i,int j){ edge[tot].to=j;edge[tot].next=head[i];head[i]=tot++;}void init(){ tot=0; memset(ind,0,sizeof(ind)); memset(head,-1,sizeof(head));}int main(){ //freopen("test.txt","r",stdin); int n,m,i,j,k; while(scanf("%d%d",&n,&m)!=EOF) { init(); int flag=0; while(m--) { scanf("%d%d",&i,&j); if(i==j) flag=1; if(flag) continue; ind[i]++; addedge(j,i); } topo(n); if(iq<n||flag) printf("-1\n"); else { int s=0; for(i=0;i<=t;i++) s+=ans[i]*(i+888); printf("%d\n",s); } } return 0;}
hdu2647 Reward 拓扑排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。