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

发表于 更新于 分类于 阅读次数：
2019牛客多校5H题 拓扑排序BFS 算法学习日常 我的头铁(~~比赛因此卡1小时去谷歌~~)写法,先直接用cin.get()吃掉t和lentmp后面的回车,再getline(),否则getline会吃那个回车而导致少读数据

算法学习日常第一天

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题

每日一句叨叨

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

若命运不公，那就和它斗到底！