#include <iostream> #include <vector> #include <algorithm> using namespace std; const int N=300; int n; bool skas[N]; int blok[N]; vector<int> przed[N]; vector<int> znajdzNajdl() { int lPo[N]={}, skad[N]; for (int i=0; i<n; ++i) if (!skas[i]) for (int j=0; j<przed[i].size(); ++j) ++lPo[przed[i][j]]; vector<int> biez, nast; for (int i=0; i<n; ++i) if (!skas[i] && lPo[i]==0) { biez.push_back(i); skad[i]=-1; } while (!biez.empty()) { nast.clear(); for (int i=0; i<biez.size(); ++i) { int b=biez[i]; for (int j=0; j<przed[b].size(); ++j) { int c=przed[b][j]; if (skas[c]) continue; if (--lPo[c]==0) { nast.push_back(c); skad[c]=b; } } } biez.swap(nast); } vector<int> wyn; if (!nast.empty()) for (int x=nast[0]; x!=-1; x=skad[x]) wyn.push_back(x); return wyn; } int licz(int k) { vector<int> najdl=znajdzNajdl(); int wyn=najdl.size(); if (wyn==0 || k==0) return wyn; for (int i=0; i<najdl.size(); ++i) { int v=najdl[i]; if (1<++blok[v]) continue; if (!skas[v]) { skas[v]=true; wyn=min(wyn, licz(k-1)); skas[v]=false; } } for (int i=0; i<najdl.size(); ++i) --blok[najdl[i]]; return wyn; } int main() { ios_base::sync_with_stdio(false); int m, k; cin>>n>>m>>k; for (int i=0; i<m; ++i) { int x, y; cin>>x>>y; --x; --y; przed[y].push_back(x); } cout<<licz(k)<<endl; 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 85 86 87 88 89 90 91 92 93 94 | #include <iostream> #include <vector> #include <algorithm> using namespace std; const int N=300; int n; bool skas[N]; int blok[N]; vector<int> przed[N]; vector<int> znajdzNajdl() { int lPo[N]={}, skad[N]; for (int i=0; i<n; ++i) if (!skas[i]) for (int j=0; j<przed[i].size(); ++j) ++lPo[przed[i][j]]; vector<int> biez, nast; for (int i=0; i<n; ++i) if (!skas[i] && lPo[i]==0) { biez.push_back(i); skad[i]=-1; } while (!biez.empty()) { nast.clear(); for (int i=0; i<biez.size(); ++i) { int b=biez[i]; for (int j=0; j<przed[b].size(); ++j) { int c=przed[b][j]; if (skas[c]) continue; if (--lPo[c]==0) { nast.push_back(c); skad[c]=b; } } } biez.swap(nast); } vector<int> wyn; if (!nast.empty()) for (int x=nast[0]; x!=-1; x=skad[x]) wyn.push_back(x); return wyn; } int licz(int k) { vector<int> najdl=znajdzNajdl(); int wyn=najdl.size(); if (wyn==0 || k==0) return wyn; for (int i=0; i<najdl.size(); ++i) { int v=najdl[i]; if (1<++blok[v]) continue; if (!skas[v]) { skas[v]=true; wyn=min(wyn, licz(k-1)); skas[v]=false; } } for (int i=0; i<najdl.size(); ++i) --blok[najdl[i]]; return wyn; } int main() { ios_base::sync_with_stdio(false); int m, k; cin>>n>>m>>k; for (int i=0; i<m; ++i) { int x, y; cin>>x>>y; --x; --y; przed[y].push_back(x); } cout<<licz(k)<<endl; return 0; } |