【noip模拟赛4】找啊找啊找BF 拓扑排序
描述 ? sqybi上次找GF的工作十分不成功,于是依旧单身的他在光棍节前的某天突发奇想,要给自己找一个BF(这里指的是男性的好朋友……),这样既可以和人分享内心的压抑(路人甲:压抑还分享么……),也可以保证自己能够有资格过今年的光棍节。 这次sqybi为了增加成功率,希望先对他提前确定的几个人定一下重要度。每个人的重要度都用一个自然数表示,这里的自然数包括0。 现在sqybi的心目中已经有了一些对于这些人的看法。他对于某个人的看法是基于另一个人的基础之上的,比如他会认为a比b的重要度至少大k。 现在给定sqybi心目中所有的看法,现在希望你能够对这些人排出一些重要度,使得在这些重要度满足所有看法的同时每个人的重要度都最低。 ? 输入 ? 第一行是两个正整数n和m,表示sqybi确定的人数以及sqybi心中的看法数目。这n个人的编号是1到n。 接下来m行,每行三个正整数a,b,k,表示编号为a的人的重要度比编号为b的人的重要度至少大k。 ? 输出 ? 仅一行,有n个正整数,表示n个人满足条件时的最小重要度。 ? 输入样例 1? 5 6 1 2 2 1 3 1 3 2 2 5 4 1 5 3 3 4 2 3 输出样例 1 3 0 2 3 5 #include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m); #define RIII(n,m,k) scanf("%d%d%d",&m,&k) #define RS(s) scanf("%s",s); #define LL long long #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define N 10005 int in[N]; vector<int>edge[N]; vector<int>d[N]; //一开始我写成mp[N][N]就错了 奇怪 long ans[N]; int main() { int n,m; RII(n,m); while(m--) { int a,b,c; RIII(a,c); in[a]++; edge[b].push_back(a); d[b].push_back(c); } queue<int>q; for(int i=1;i<=n;i++) //n 节点的总数 if(in[i]==0) q.push(i); //将入度为0的点入队列 while(!q.empty()) { int p=q.front(); q.pop(); if(edge[p].size()) for(int i=0;i<edge[p].size();i++) { int y=edge[p][i]; ans[y]=max(ans[y],ans[p]+d[p][i]); in[y]--; if(in[y]==0) q.push(y); } } printf("%ld",ans[1]); rep(i,2,n) printf(" %ld",ans[i]); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |