首页 > 代码库 > Day1：T1 模拟 T2 拓扑排序
Day1：T1 模拟 T2 拓扑排序
T1：模拟
自己第一天的简直跟白痴一样啊...模拟都会打错..
当时貌似在更新最大值的时候打逗比了...
if((sum[x]==max && x<maxh) || sum[x]>max){
max=sum[x];
maxh=x;
//现在（也就是9月+）再看，脑袋里只有sortsortsort，连最基本的更新最大指都忘了....智商唉....
附上代码：
#include<cstdio>#include<cstring>using namespace std;int f[9]={10,8,6,5,4,3,2,1};int n,m,x,max=0,maxh=10000100;long long sum[1000001];bool cmp(int a,int b){ return a>b;}int main(){ freopen("rank.in","r",stdin); freopen("rank.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ for(int j=0;j<8;j++){ scanf("%d",&x); sum[x]+=f[j]; if((sum[x]==max && x<maxh) || sum[x]>max){ max=sum[x]; maxh=x; } } printf("%d\n",maxh); } return 0;}
T2：拓扑排序
这是我在长乐学的第一个学到的东西...蒟蒻表示看懂了这个算法很开森..
当时由于我是一个记性特不好的人，越发的意识到写写题解的重要性！
首先先介绍一下拓扑排序吧
如果一个点y之前有另一个点x指向它，那么出渡c[x]++；入渡r[y]++;
c[]就表示x的出渡，也就是记录他指向多少个点；
r[]就表示y的入渡，也就是记录有多少点指向它；
这里还需要一个二维数组a[][]
让a[x][c[x]]=y;
也就是用来记录以x为起点，它所连的第c[x]个点是y;
理解了数组的含义，接下来模拟一下即可：
稍微讲一下思路吧：
1.选择一个入度为0的点存入ans[]里，输入；但是这里要注意若一开始就有多个点的入度为0，最后一个搜的点先输出。
2.删除和这个点有关联的边
3.ans里的指针tot--,如果存在入度为0的点，tot++;输出当前搜到的点，不然就输出之前存的；
4.while(num<n);
复杂度O(V+E);
模板代码：
for(int i=1;i<=m;i++){//m为关系的次数 scanf("%d%d",&x,&y); c[x]++; a[x][c[x]]=y; r[y]++;}for(int i=1;i<=n;i++){//n为总的个数 if(r[i]==0) ans[++tot]=i;}while(num<n){ temp=ans[tot]; printf("%d",temp);//这里注意是从入渡为0的最后一个点先输出的 tot--; num++; for(int j=1;j<=c[temp];j++){ r[a[temp][j]]--; } for(int j=1;j<=n;j++){ if(r[a[temp][j]]==0){ tot++; ans[tot]=j; break; } }}当然这一道题吧，除了用拓扑之外，还需要注意判断是否满足条件
这里判断的方法是
1.如果不存在入渡为0的点，也就是存在一个环的时候，不满足条件
2.在拓扑过程中，找不到入度为0的点，也不满足；
PS:这里还需要注意一个题目中的小细节，也就是在入渡都为0的情况下，先输出号数比较小的；
//找到了就直接break这样可以保证找到的是最小的编号
附上ccy大神的注释：
//拓扑排序 给出注释program event;var f:array[0..1001,0..1001] of boolean; a:array[0..100000] of longint; b:array[0..1001] of longint; n,m,x,y,t,i,j,top:longint;begin fillchar(f,sizeof(f),false); fillchar(a,sizeof(a),0); fillchar(b,sizeof(b),0); readln(n,m); for i:=1 to m do begin readln(x,y); if not f[x,y] then//如果读入的关系没有重复 begin f[x,y]:=true;//置为已用过 inc(a[y]);//对应的较晚发生的历史事件的入度递增 end; end; for i:=1 to n do begin t:=0;//用来判断是否有找到一个入度为0的节点 for j:=1 to n do if a[j]=0 then begin t:=j;//如果找到了就直接break这样可以保证找到的是最小的编号 break; end; for j:=1 to n do if f[t,j] then//如果这个点的出度对应的也存在 begin dec(a[j]);//其出度递减 f[t,j]:=false;//这条线去除 end; inc(top);//递增栈 b[top]:=t;//入栈 a[t]:=-1;//该节点的入度变成1 if t=0 then//如果t=0就代表没有将任何节点都找到 就直接输出错误信息退出 begin writeln(‘Error!‘); halt; end; end; for i:=1 to top do writeln(b[i]);//从早到晚打印每一个历史事件end.
这里没有按照书本上的模板打，但是思路相同，貌似ccy的打法会更简单直观一点...学习了
自己就不再重打一遍了
Day1：T1 模拟 T2 拓扑排序