首页 > 代码库 > UESTC 916 方老师的分身III --拓扑排序

UESTC 916 方老师的分身III --拓扑排序

2024-07-08 07:01:43   215人阅读

做法：

如果有a<b的关系，则连一条a->b的有向边，连好所有边后，找入度为0的点作为起点，将其赋为最小的价值888，然后其所有能到的端点，价值加1，加入队列，删去上一个点，然后循环往复，直到队列为空，即每个点都赋予了一个权值为止。

代码：

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <queue>using namespace std;#define N 10007int first[N],in[N],candy[N];int tot;struct node{    int u,v,next,w;}G[20006];void addedge(int u,int v){    G[tot].u = u;    G[tot].v = v;    G[tot].w = 1;    G[tot].next = first[u];    first[u] = tot++;}int main(){    int n,m,cnt,i,j,x;    int a,b;    queue<int> que;    while(scanf("%d%d",&n,&m)!=EOF)    {        memset(in,0,sizeof(in));        while(!que.empty())            que.pop();        memset(first,-1,sizeof(first));        tot = 0;        for(i=0;i<m;i++)        {            scanf("%d%d",&a,&b);            addedge(b,a);            in[a]++;        }        for(i=1;i<=n;i++)        {            if(in[i] == 0)            {                que.push(i);                candy[i] = 888;            }        }        cnt = 0;        while(!que.empty())        {            x = que.front();            que.pop();            cnt++;            for(int e=first[x];e!=-1;e=G[e].next)            {                in[G[e].v]--;                if(in[G[e].v] == 0)                {                    que.push(G[e].v);                    candy[G[e].v] = candy[x]+1;                }            }        }        if(cnt < n)            puts("-1");        else        {            int sum = 0;            for(i=1;i<=n;i++)                sum += candy[i];            printf("%d\n",sum);        }    }    return 0;}
View Code

 


联系
我们