题意
给定$n$个人的$m$个关系，形如:$x, y, z$，表示$x$比$y$的$z$学科成绩高。求1号学生在最坏和最好情况下的排名。
学科数目$\leq 3,2\leq n \leq 50000, 2\leq m \leq 10^6$。
思路
考场上面想到的是SPFA求最长路，于是就爆0了。这么做显然是有问题的，因为对排名的并列理解不清楚。e.g.如果2~5的分数是100，1的分数是90，那么2~5并列第一，1是第五，而非第二。
明确了这一点之后就可以建图了。我们想要知道一定比1号排名高的和一定比1号排名低的分别有多少人。先考虑$k=1$的情况。对于一个关系$(x,y)$，分别在两张图中连有向边$u\rightarrow v$和$v\rightarrow u$。再BFS就可以得知所求的量。于是最好的排名=一定比1号排名高的人数+1，最坏的排名=$n$-一定比1号排名低的人数。
对于$k>1$的情况，对每一科目一定比1号排名高的人与一定比1号排名低的人分别取交集即可。
时间复杂度为$O[2k(n+m)]$。
代码
#include <bits/stdc++.h>
#define reg register
using namespace std;
const int MAXN = 5e4, MAXM = 1e6;
struct Edge{
int v,next;
};
struct Solver {
int e_ptr, head[MAXN+10];
Edge E[(MAXM<<1)+10];
bool vis[MAXN+10];
void AddEdge(int u, int v){
E[++e_ptr]=(Edge){v,head[u]}; head[u]=e_ptr;
}
void BFS() {
queue<int> Q;
vis[1]=true; Q.push(1);
memset(vis, 0, sizeof(vis));
while(!Q.empty()) {
int u=Q.front(); Q.pop();
for(int j=head[u];j;j=E[j].next) {
int v=E[j].v;
if(vis[v]) continue;
vis[v]=true; Q.push(v);
}
}
}
} sol[7];
int N, K, M;
inline int readint() {
reg int f=1, r=0; reg char c=getchar();
while(!isdigit(c)) { if(c=='-')f=-1; c=getchar(); }
while(isdigit(c)) { r=r*10+c-'0'; c=getchar(); }
return f*r;
}
void Init() {
int u, v, z;
N=readint(); K=readint(); M=readint();
for(int i=1; i<=M; i++) {
u=readint(); v=readint(); z=readint();
sol[z].AddEdge(u, v);
sol[z+K].AddEdge(v, u);
}
}
void Work() {
int Cnt1=0, Cnt2=0;
static bool Fr[MAXN+10], Bk[MAXN+10];
for(int i=1; i<=K*2; i++) sol[i].BFS();
for(int i=1; i<=N; i++) {
Fr[i]=true;
for(int j=K+1; j<=2*K; j++)
Fr[i] = Fr[i] && sol[j].vis[i];
}
for(int i=1; i<=N; i++) {
Bk[i]=true;
for(int j=1; j<=K; j++)
Bk[i] = Bk[i] && sol[j].vis[i];
}
for(int i=1; i<=N; i++) {
if(Fr[i]) Cnt1++;
else if(Bk[i]) Cnt2++;
}
printf("%d %d", N-Cnt2, Cnt1+1);
}
int main() {
Init(); Work();
return 0;
}
