#include <iostream> #include <vector> #include <math.h> using namespace std; vector <int> tab[301]; int n, m, k; int temp_1, temp_2; int lan_p[301]; int lan_n[301]; bool tabb[301]; int kompil() { for (int i = 0; i < 301; i++) { lan_p[i] = 0; lan_n[i] = 0; } for (int i = 0; i < 301; i++) { for (int j = 0; j < tab[i].size(); j++) { if (lan_n[tab[i][j]] < lan_n[i] + 1&&tabb[tab[i][j]]) { lan_n[tab[i][j]] = lan_n[i] + 1; } } } for (int i = 300; i >= 0; i--) { for (int j = tab[i].size() - 1; j >= 0; j--) { if (lan_p[i] < lan_p[tab[i][j]] + 1 && tabb[tab[i][j]]) { lan_p[i] = lan_p[tab[i][j]] + 1; } } } return 0; } int main() { int kon, min_i = 400, min_n=500,temp; cin >> n >> m >> k; for (int i = 0; i < m; i++) { cin >> temp_1 >> temp_2; tab[temp_1].push_back(temp_2); } for (int i = 0; i < 301; i++) { tabb[i] = true; } kompil(); if (k != n) { for (int x = 0; x < k; x++) { min_i = 400; min_n = 500; for (int y = 1; y < 301; y++) { temp = abs(lan_n[y] - lan_p[y]); if (temp < min_n && !(lan_n[y] == 0 && lan_p[y] == 0)) { min_n = temp; min_i = y; } } tab[min_i].clear(); tabb[min_i] = false; kompil(); kon = 0; for (int y = 1; y < 301; y++) { if (kon < lan_p[y]) { kon = lan_p[y]; } if (kon < lan_n[y]) { kon = lan_n[y]; } } } } if (n == k) { cout << "0"; } else { cout << kon+1; } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 | #include <iostream> #include <vector> #include <math.h> using namespace std; vector <int> tab[301]; int n, m, k; int temp_1, temp_2; int lan_p[301]; int lan_n[301]; bool tabb[301]; int kompil() { for (int i = 0; i < 301; i++) { lan_p[i] = 0; lan_n[i] = 0; } for (int i = 0; i < 301; i++) { for (int j = 0; j < tab[i].size(); j++) { if (lan_n[tab[i][j]] < lan_n[i] + 1&&tabb[tab[i][j]]) { lan_n[tab[i][j]] = lan_n[i] + 1; } } } for (int i = 300; i >= 0; i--) { for (int j = tab[i].size() - 1; j >= 0; j--) { if (lan_p[i] < lan_p[tab[i][j]] + 1 && tabb[tab[i][j]]) { lan_p[i] = lan_p[tab[i][j]] + 1; } } } return 0; } int main() { int kon, min_i = 400, min_n=500,temp; cin >> n >> m >> k; for (int i = 0; i < m; i++) { cin >> temp_1 >> temp_2; tab[temp_1].push_back(temp_2); } for (int i = 0; i < 301; i++) { tabb[i] = true; } kompil(); if (k != n) { for (int x = 0; x < k; x++) { min_i = 400; min_n = 500; for (int y = 1; y < 301; y++) { temp = abs(lan_n[y] - lan_p[y]); if (temp < min_n && !(lan_n[y] == 0 && lan_p[y] == 0)) { min_n = temp; min_i = y; } } tab[min_i].clear(); tabb[min_i] = false; kompil(); kon = 0; for (int y = 1; y < 301; y++) { if (kon < lan_p[y]) { kon = lan_p[y]; } if (kon < lan_n[y]) { kon = lan_n[y]; } } } } if (n == k) { cout << "0"; } else { cout << kon+1; } return 0; } |