*51nod 1815

从若干个数中选出最大的任意两数取模之后的结果

严格次大值

对于此题

首先缩点

然后拓扑排序

维护到达每个点的最大值与严格次大值

感觉思路与代码都OK啊

then....

#include 
#include 
#include 
#include 
#include 
#include <string>
#include 
#include using namespace std;#define LL long long#define gc getchar()
inline int read() {int x = 0; char c = gc; while(c < '0' || c > '9') c = gc;
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc; return x;}
inline LL read_LL() {LL x = 0; char c = gc; while(c < '0' || c > '9') c = gc;
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc; return x;}
#undef gcconst int N = 4e5 + 10, M = 2e6 + 10;
int n, m, S, Q;
int A[N];int Dfn[N], Low[N], Belong[N], Beljs, Tim;
bool vis[N];
int Stack[N], topp;pair <int, int> Pair[N];
struct Node {int u, v, nxt;} G[M];
int head1[N], cnt;inline void Link(int u, int v) {G[++ cnt].v = v; G[cnt].nxt = head1[u]; head1[u] = cnt;}void Tarjan(int u) {Dfn[u] = Low[u] = ++ Tim;vis[u] = 1;Stack[++ topp] = u;for(int i = head1[u]; ~ i; i = G[i].nxt) {int v = G[i].v;if(!Dfn[v]) {Tarjan(v);Low[u] = min(Low[u], Low[v]);} else if(vis[v]) Low[u] = min(Low[u], Low[v]);}if(Low[u] == Dfn[u]) {int Max = 0, CMax = 0;Max = A[u];vis[u] = 0; Belong[u] = ++ Beljs;Pair[Beljs].first = A[u]; Pair[Beljs].second = -1;while(Stack[topp] != u) {int a  = Stack[topp];vis[a] = 0;Belong[a] = Beljs;topp --;if(A[a] > Max) {CMax = Max, Max = A[a];}else if(A[a] != Max) CMax = max(CMax, A[a]);Pair[Beljs] = make_pair(Max, CMax);} topp --;}
}Node E[M];
int head2[N], Du[N];inline void ReLink(int u, int v) {Du[v] ++; E[++ cnt].v = v; E[cnt].nxt = head2[u]; head2[u] = cnt;}int use[N];void Rebuild() {for(int i = 1; i <= Beljs; i ++) head2[i] = -1;cnt = 0;for(int u = 1; u <= n; u ++)for(int i = head1[u]; ~ i; i = G[i].nxt) {int v = G[i].v;if(Belong[u] != Belong[v] && use[Belong[v]] != u) {use[Belong[v]] = u;
//                cout << Belong[u] << " " << Belong[v] << "\n";
                ReLink(Belong[u], Belong[v]);    }}
}int Que[N];bool beuse[N];void Topsort() {int h = 1, t = 0;
//    for(int i = 1; i <= Beljs; i ++) if(Du[i] == 0) Que[++ t] = i;Que[++ t] = Belong[S];while(h <= t) {int topu = Que[h ++];beuse[topu] = 1;for(int i = head2[topu]; ~ i; i = E[i].nxt) {int v = E[i].v;Du[v] --;if(Du[v] == 0) Que[++ t] = v;int B[5];
//            cout << Pair[topu].first << " " << Pair[topu].second << " " << Pair[v].first << " " << Pair[v].second << "\n";B[1] = Pair[topu].first, B[2] = Pair[topu].second, B[3] = Pair[v].first, B[4] = Pair[v].second;sort(B + 1, B + 5);Pair[v].first = B[4];int j = 3;while(B[j] == B[4]) j --;Pair[v].second = B[j];}}
}int main() {
//    srand(time(0) - 99999);
//    freopen("gg.in", "r", stdin);
//    freopen("gg.out", "w", stdout);n = read(), m = read(), Q = read(), S = read();for(int i = 1; i <= n; i ++) A[i] = read();for(int i = 1; i <= n; i ++) head1[i] = -1;for(int i = 1; i <= m; i ++) {int u = read(), v = read();Link(u, v);}for(int i = 1; i <= n; i ++) if(!Dfn[i])Tarjan(i);
//    for(int i = 1; i <= Beljs; i ++) {
//        cout << Pair[i].first << " " << Pair[i].second << "\n";
//    }
//    return 0;
    Rebuild();
//    for(int i = 1; i <= Beljs; i ++) {
//        for(int j = head2[i]; ~ j; j = E[j].nxt) {
//            int v = E[j].v;
//            cout << i << " " << v << "\n";
//        }
//    }
    Topsort();for(int i = 1; i <= Q; i ++) {int a = read();if(beuse[Belong[a]] == 0) cout << -1 << " ";else cout << Pair[Belong[a]].second << " ";//    if(ans == 0) cout << -1 << " ";
//        cout << ans << " ";
    }return 0;
}
/*
8 10 5 1
5 5 5 7 5 5 5 5
1 2
2 3
3 1
3 4
5 1
6 5
1 6
6 8
8 7
7 6
1 2 3 4 5
*/ 

转载于:https://www.cnblogs.com/shandongs1/p/9594371.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！