拓扑排序以及C++读取空行[算法学习日常1/100]

算法学习日常第一天

2019年8月2日

  • 今天上午,重新认识算法的全貌各种资源及知识点总结

  • 并且还了解到了常见错误写法,当然自己当年也写过很多错误

  • 下午先是补牛客5的多校G题的dp—接着昨天的补都补了90mins(含对着手写第一遍),还是太菜了

  • 然后补H题,发现自己昨天写了3个小时的这个题目不是字符串插入题…而是一个拓扑排序题..真的自己菜得可怕..写错分类怎么可能做对,然后自己又焦虑了很久,知道2019年8月2日15:48:15才静下来认真地学习拓扑排序
    • 拓扑排序在紫书上学了下,就是把点对关系看成一个图里面的指向关系,即把每一个点对看做小数指向大数的有向边,如果图没有有向环的话,说明是可以的,否则是不行的
    • 记自己头铁处理空行读入,搞了整整一个小时读取空行

拓扑排序以及空行头铁见代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
/*
2019年8月2日19:25:05
拓扑排序bfs

拓扑排序算法思想
1、在AOV网络中选一个没有直接前驱的顶点, 并输出之;
2、从图中删去该顶点, 同时删去所有它发出的有向边;--->(我下面的题目使用stop实现删除)
3、重复以上步骤, 直到
◆ 全部顶点均已输出,拓扑有序序列形成,拓扑排序完成;
◆ 或者图中还有未输出的顶点,但已跳出处理循环。这说明图中还剩下一些顶点,
它们都有直接前驱,再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。
*/
#include<bits/stdc++.h>
using namespace std;
const int M = 1e4+5;
int n,m,lentmp;
string s[10][10];
/*用string本来可以不用下面的len*/
int len[10][10];
int it[10][10];
string ans,t;
bool check();
bool solve();

int main(){
ios::sync_with_stdio(false);cin.tie(0);
cin>>n>>m;
for(int i=0;i<m*(m-1)/2;i++){
cin>>t>>lentmp;
int x=t[0]-'a',y=t[1]-'a';
if(x>y) swap(x,y);
len[x][y] = lentmp;
// if(lentmp) cin>>s[x][y];
/*我的头铁(~~比赛因此卡1小时去谷歌~~)写法
先直接用cin.get()吃掉t和lentmp后面的回车
再getline(),
否则getline会吃那个回车而导致少读数据*/
cin.get();
getline(cin,s[x][y]);
}
if(!solve()) puts("-1");

return 0;
}

/*暴力检测每队关系是否和整个串中的样子是一样的
法二: 也可以每一对关系得到一个ans的tmp串,然后再去==判断
但是效率低
*/
bool check(){
for(int i=0;i<m;i++){
for(int j=i+1;j<m;j++){
int now = 0;
for(int k=0;k<n;k++){
if(ans[k]=='a'+i||ans[k]=='a'+j){
if(ans[k]!=s[i][j][now]) return 0;
now++;
}
}
if(now!=len[i][j]) return 0;
}
}
return 1;
}

bool solve(){
for(int i=0;i<n;i++){
/* 这里是每个大串的排序关系-通过m次的关系问询确定的

注意前面巧妙地处理出了j小于k--->这就是拓扑排序的思路

1.对没有出现过的关系(即s[j][k]的那一维全为空)stop[j]和stop[k]全都赋值为1
2.对于到最后了的关系(即s[j][k][]='\0')全赋空


因为有m*(m-1)/2 对 关系,也就是每两个都有比较,所以一定能够得出最前面的一个字符..所以就完美了!

这里每次stop都会清零!*/
bool stop[10] = {};
for(int j=0;j<m;j++){
for(int k=j+1;k<m;k++){
if(!s[j][k][it[j][k]]) stop[j]=stop[k]=1;
else if(s[j][k][it[j][k]]=='a'+j) stop[k]=1;
else stop[j] = 1;
}
}
bool done = false;
for(int j=0;j<m;j++){
if(!stop[j]){
ans+='a'+j;
for(int k=0;k<m;k++){
if(k<j) it[k][j]++;
else if(k>j) it[j][k]++;
}
done = true;
break;
}
}
if(!done) return 0;
}
if(!check()) return 0;
cout<<ans<<endl;
return 1;
}
  • 晚上成功补完H题和I题,发现好像没有时间补B题了,明天上午来补一下B题

每日一句叨叨

杜月笙知道成功需要代价,他想为自己洗白(小时候家里穷只能混黑帮),为整个帮派洗白,但穿了大半辈子长褂(为了不露出纹身),让自己的说书先生给自己讲了大半辈子学,也为上海的繁荣安定做了大半辈子贡献,但却最终未被认可(通过人脉被选之为一个参议长,但蒋介石让他自己退位),但杜月笙却永远被后人被历史铭记

若命运不公,那就和它斗到底!

点击查看

本文标题:拓扑排序以及C++读取空行[算法学习日常1/100]

文章作者:单林敏

发布时间:2019年08月02日 - 22:22:13

最后更新:2019年10月17日 - 19:20:27

原始链接:https://www.wolfdan.cn/写封情书给算法1/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

-------------------本文结束 感谢您的阅读-------------------
0%