1192啥意思_有向图的拓扑排序算法

全栈程序员-站长 • 2022年8月9日下午2:36 • 未分类 • 阅读 9

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出，Yali Company总经理Mr.Z心情好，决定给每位员工发奖金。

公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。

于是Mr.Z下令召开 m 方会谈。

每位参加会谈的代表提出了自己的意见：“我认为员工 a 的奖金应该比 b 高！”

Mr.Z决定要找出一种奖金方案，满足各位代表的意见，且同时使得总奖金数最少。

每位员工奖金最少为100元，且必须是整数。

输入格式
第一行包含整数 n,m，分别表示公司内员工数以及参会代表数。

接下来 m 行，每行 2 个整数 a,b，表示某个代表认为第 a 号员工奖金应该比第 b 号员工高。

输出格式
若无法找到合理方案，则输出“Poor Xed”；

否则输出一个数表示最少总奖金。

数据范围
1≤n≤10000,
1≤m≤20000

输入样例：
2 1
1 2
输出样例：
201

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
const int M = 20000 + 10;
struct Edge{ 
   
    int v,w,next;
}edge[M];
int head[N],cnt;
    int n,m;
void add(int u,int v){ 
   
    edge[cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}
int vis[N],in[N],dist[N];
int q[N],hh = 0,tt = 0;
int bfs(){ 
   
    for(int i = 1;i <= n;i ++){ 
   
        if(!in[i]){ 
   
            q[tt ++] = i;
            dist[i] = 100;
        }
    }
    int cnt = 0;
    while(hh < tt){ 
   
        int t = q[hh ++];
        cnt ++;
        for(int i = head[t];~i;i = edge[i].next){ 
   
            int v = edge[i].v;
            if(dist[v] <= dist[t] + 1){ 
   
                dist[v] = dist[t] + 1;
            }
            in[v] --;
            if(!in[v])q[tt ++] = v;
        }
    }
    int res = 0;
    for(int i = 1;i <= n;i ++){ 
   
        res += dist[i];
    }
    if(cnt < n)return -1;
    return res;
}
int main(){ 
   
    cin>>n>>m;
    int x,y;
    memset(head,-1,sizeof head);
    for(int i = 0;i < m;i ++){ 
   
        cin>>x>>y;
        add(y,x);
        in[x] ++;
    }
    int t = bfs();
    if(t == -1)cout<<"Poor Xed"<<endl;
    else cout<<t<<endl;
    return 0;
}