拓扑排序_走多远

蓝桥账户中心

拓扑排序: 用于查找先后顺序的 将最前面的定义为入度为0的点 不断遍历 拓扑排序会出现多种解

实现过程

1. 用队列存储点的先后顺序()

#include <bits/stdc++.h>

#define endl '\n'
#define maxn 1000005
#define ll long long

using namespace std;

ll dist[maxn];
vector< vector<int> > graph(maxn);
vector<int> ans;  //记录边的顺序
queue<int> q;
int deg[maxn];

void initGraph( int n) {  //初始化邻接表
    for( int i = 0; i < n; ++i ){
        graph[i].clear();
    }
}

void addEdge( int u, int v){  //添加邻边
    graph[u].push_back(v);
    ++deg[v];  //添加度
}

bool topoSort( int n){
    for ( int i = 0; i < n; ++i ){  //先找到入度为0的点
        if ( deg[i] == 0 ){
            q.push(i);
            --deg[i];
        }
    }
    while (!q.empty()){
    
	    int u = q.front();
        q.pop();
        ans.push_back(u);  //将符合条件的点加入顺序表
        for ( int i = 0; i < graph[u].size(); ++i ){
            int v = graph[u][i];
            --deg[v];
            if ( deg[v] == 0 ){  //继续查找符合条件的点
                q.push(v);
            }
        }
    }
    return ans.size() == n;
}

int main() {

    int n; cin >> n;
    int m; cin>> m;
    initGraph( n);  //初始化边

    for ( int i = 0; i < m; ++i ){
        int u; cin >> u;
        int v; cin >> v;
        addEdge( u - 1, v - 1);
    } 

    ll ret = 0; 

    if ( topoSort(n)){
        for ( int i = n - 1; i >= 0; --i ){
            int u = ans[i];
            for ( int j = 0; j < graph[u].size(); ++j ){
                int v = graph[u][j];
                dist[u] = max( dist[u], dist[v] + 1);
            }
            ret = max( ret, dist[u]);
        } 
        cout << ret << endl;
    }else{
        cout << ret << endl;
    }

    return 0;
}

但是这一题 就有点不太友好 需要自己发现隐含条件

蓝桥账户中心

因为拓扑排序适用于 有向无环图 但是这题 就只是一个案例 就是无相有环图 但是仔细观察题目 有一个 

那么就变成一个有向无环图了 

这里是代码

#include<bits/stdc++.h>

#define endl '\n'
#define maxn 100005
#define ll long long

using namespace std;

int a[maxn];
int deg[maxn];
ll dist[maxn];
vector< vector<int> > graph(maxn);
vector<int> ans;
queue<int> q;

void initGrapg(int n ){  //初始化graph
    for ( int i = 0; i < n; ++i ){
        graph[i].clear();
    }
}

void addEdge(int u, int v ){  //建边
    if ( a[u] < a[v]){  //只能去到观赏值大的
        graph[u].push_back(v);
        ++deg[v];
    }
    if ( a[v] < a[u]){
        graph[v].push_back(u);
        ++deg[u];
    }
}

void topoSort( int n){
    for ( int i = 0; i < n; ++i ){
        if ( deg[i] == 0 ){
            q.push(i);
            //--deg[i];
        }
    }
    while ( !q.empty()){
        int u = q.front();
        ans.push_back(u);
        q.pop();
        for ( int i = 0; i < graph[u].size(); ++i){
            int v = graph[u][i];
            --deg[v];
            if ( deg[v] == 0 ){
                q.push(v);
            }
        }
    }
}


int main() {

    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n; cin >> n;
    int m; cin >> m;

    initGrapg(n);

    for ( int i = 0; i < n; ++i ){  //输入观赏值
        cin >> a[i];
    }

    for ( int i = 0; i < m; ++i ){  //建边 
        int u; cin >> u;
        int v; cin >> v;
        addEdge(u - 1, v - 1);  //位置偏移
    }

    topoSort(n);

    ll ret = 0;

    for ( int i = n - 1; i >= 0; --i ){
    	ll tmp = 0; 
        int u = ans[i];
        for ( int j = 0; j < graph[u].size(); ++j ){
            int v = graph[u][j];
            tmp = max( tmp, dist[v]);
        }
        dist[u] = max(dist[u], tmp + a[u]);
        ret = max( ret, dist[u]); 
    }

    cout << ret << endl;

    return 0;
}

蓝桥账户中心

这一道的话其实就是有一个陷阱

刚开始的时候 我直接用like数组保存好感度 忽略了可以有不同的边到达相同的边

借着这个机会 了解了一下pair的用法

#include <bits/stdc++.h>

#define endl '\n'
#define ll long long
#define inf INT_MIN
#define maxn 200005

using namespace std;

int dp[maxn];  //代表从最开始的边开始 到达第i个点的最大好感度
vector<int> ans;
vector< vector< pair<int, int> > > graph(maxn);
queue<int> q;
int deg[maxn];

void initGraph( int n){  //初始化邻接表
    for (int i = 0; i < n; ++i ){
        graph[i].clear();
        dp[i] = inf;
        deg[i] = 0; 
    }
    dp[0] = 0;  //最开始 好感度为0
}

void addEdge( int u, int v, int w){  //添加邻边
    graph[u].push_back({v, w});
    ++deg[v];
}

void topoSort( int n ){
    for ( int i = 0; i < n; ++i ){
        if (deg[i] == 0 ){
            --deg[i];
            q.push(i);
        }
    }
    while ( !q.empty()){
        int u = q.front();
        q.pop();
        ans.push_back(u);
        for ( int i = 0; i < graph[u].size(); ++i ){
            int v = graph[u][i].first;
            --deg[v];
            if ( deg[v] == 0){
                q.push(v);
            }
        }
    }
}

int main() {

    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n; cin >> n;
    int m; cin >> m;

    initGraph(n);  //初始化邻接表

    for ( int i = 0; i < m; ++i ){
        int u; cin >> u;
        int v; cin >> v;
        int w; cin >> w;
        addEdge( u - 1, v - 1, w);

    }

    topoSort(n);

    int ret = 0;

    for ( int i = 0; i < n; ++i ){  //这次从前往后遍历 因为要到达终点 到达终点需要前->后
        int u = ans[i];
        for ( int j = 0; j < graph[u].size(); ++j ){
        	int v = graph[u][j].first; 
            int like = graph[u][j].second; 
            dp[v] = max( dp[v], dp[u] + like);
        }
    } 

    for ( int i = 0; i < n; ++i ){
        if (dp[i] >= 100 && graph[i].size() == 0 ){
            ++ret;
        }
    }

    cout << ret << endl;

    return 0;
}