3371 - 银河
银河中的恒星浩如烟海，但是我们只关注那些最亮的恒星。我们用一个正整数来表示恒星的亮度，数值越大则恒星就越亮，恒星的亮度最暗是1。现在对于N 颗我们关注的恒星，有M 对亮度之间的相对关系已经判明。你的任务就是求出这N 颗恒星的亮度值总和至少有多大。
数据范围与约定
对于30% 的数据，N≤100。
对于 100% 的数据，N≤100 000，M≤100 000。
Input
第一行给出两个整数N 和M。
之后 M 行，每行三个整数T, A, B，表示一对恒星(A, B)之间的亮度关系。恒星的编号从1 开始。
如果 T = 1，说明A 和B 亮度相等。
如果 T = 2，说明A 的亮度小于B 的亮度。
如果 T = 3，说明A 的亮度不小于B 的亮度。
如果 T = 4，说明A 的亮度大于B 的亮度。
如果 T = 5，说明A 的亮度不大于B 的亮度。
Output
输出一个整数表示答案。
Examples
Input
5 7 1 1 2 2 3 2 4 4 1 3 4 5 5 4 5 2 3 5 4 5 1
Output
11
Hint
数据范围与约定
对于30% 的数据，N≤100。
对于 100% 的数据，N≤100 000，M≤100 000。
Solution C++
#include <cstdio> #include <cmath> #include <queue> #include <cstring> #include <climits> #include <algorithm> using namespace std; typedef long long LL; int N=0,M=0; LL Dis[100010]={0}; int len1[100010]={0},len2[100010]={0}; class data{ public: int to,next,v; }E[400010]; int line[100010]={0},tot=0; inline void Insert(int x,int y,int v){ E[++tot].to=y; E[tot].v=v; E[tot].next=line[x]; line[x]=tot; } struct node{ int pos; bool operator < (const node& b) const { Dis[pos] < Dis[b.pos]; } }now; priority_queue<node>Q; bool flag[100010]={0}; int head=1,tail=0; inline int F(int x){ return ((x%N)+N)%N; } inline bool empty(){ return head>tail; } int main(){ ///freopen("gin.in","r",stdin); //freopen("gin.out","w",stdout); scanf("%d%d",&N,&M); int t=0,a=0,b=0; for(int i=1;i<=M;++i){ scanf("%d%d%d",&t,&a,&b); if(t==1) Insert(a,b,0),Insert(b,a,0); else if(t==2) Insert(a,b,1); else if(t==3) Insert(b,a,0); else if(t==4) Insert(b,a,1); else if(t==5) Insert(a,b,0); } for(int i=1;i<=N;++i){ now.pos=i; len1[i]++; flag[i]=true; Dis[i]=1; Q.push(now); } while(!Q.empty()){ int t=Q.top().pos; Q.pop(); flag[t]=false; for(int i=line[t];i!=0;i=E[i].next){ int p=E[i].to; if(Dis[t]+E[i].v>Dis[p]){ Dis[p]=Dis[t]+E[i].v; len2[p]=len2[t]+1; if(len2[p]>N) { printf("-1\n"); exit(0); } if(!flag[p]){ len1[p]++; if(len1[p]>N){ printf("-1\n"); exit(0); } flag[p]=true; now.pos=p; Q.push(now);//Q[F(++tail)]=p; } } } } LL Ans=0; for(int i=1;i<=N;++i) Ans+=Dis[i]; printf("%lld",Ans); return 0; }
Hint
数据范围与约定
对于30% 的数据，N≤100。
对于 100% 的数据，N≤100 000，M≤100 000。