Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <vector>
- #include <queue>
- #include <algorithm>
- #include <string>
- #include <stack>
- #include <set>
- #include <map>
- #define pii pair <int,int>
- using namespace std;
- using ll = long long;
- using ld = long double;
- void cv(vector <int> &v){
- for (auto x: v) cout<<x<<' ';
- cout<<"\n";
- }
- void cvv(vector <vector <int> > &v){
- for (auto x: v) cv(x);
- cout<<"\n";
- }
- int n, mn, mx;
- vector <vector <int> > G;
- vector <pii> Edge;
- void cG(){
- for (int i = 0; i < n;++i){
- cout<<"("<<i<<"): ";
- cv(G[i]);
- }
- }
- void cEdge(){
- cout<<Edge.size()<<"\n";
- for (auto x: Edge){
- cout<<x.first+1<<' '<<x.second+1<<"\n";
- }
- }
- vector <int> lvl; //степени вершин
- bool cmp(int a, int b){
- return lvl[a] > lvl[b];
- }
- vector <int> vrt;
- vector <vector <int> > comp;
- int main()
- {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cin>>n>>mx>>mn;
- G.resize(n);
- lvl.assign(n, 0);
- for (int i = 0; i < n; ++i){
- vrt.push_back(i);
- if (G[i].size() == mn) continue;
- for (int j = 0; j < n && j != i; ++j){
- if (G[j].size() >= mn) continue;
- if (find(G[i].begin(), G[i].end(), j) == G[i].end() ){
- G[i].push_back(j);
- G[j].push_back(i);
- Edge.push_back({min(i, j), max(i, j)});
- lvl[i]++;
- lvl[j]++;
- }
- if (G[i].size() == mn){
- break;
- }
- }
- }
- sort(vrt.begin(), vrt.end(), cmp);
- //cout<<"graph\n";
- //cG();
- //cv(vrt);
- vector <int> v;
- for (int i = 0; i < n / (mn + 1); ++i){
- for (int j = (mn + 1) * i; j < (i + 1) * (mn + 1); ++j){
- //par[j] = i;
- v.push_back(j);
- }
- comp.push_back(v);
- v.clear();
- }
- for (int i = (n / (mn + 1)) * (mn + 1); i < n; ++i ){
- //par[i] = (n / (mn + 1)) * (mn + 1);
- v.push_back(i);
- //cout<<"i = "<<i<<"\n";
- }
- if (!v.empty()){
- comp.push_back(v);
- v.clear();
- for (int i = 0; i < comp[comp.size() - 1].size(); ++i){
- int u = comp[comp.size() - 1][i];
- if (lvl[u] >= mn) continue;
- sort(vrt.begin(), vrt.end(), cmp);
- for (int j = 0; j < n;++j){
- if (find(G[u].begin(), G[u].end(), vrt[j]) != G[u].end()){
- continue;
- }
- else if (lvl[vrt[j]] == mx) continue;
- else if (vrt[j] == u) continue;
- G[u].push_back(vrt[j]);
- G[vrt[j]].push_back(u);
- Edge.push_back({min(u, vrt[j]), max(u, vrt[j])});
- lvl[u]++;
- lvl[vrt[j]]++;
- if (lvl[u] == mn) break;
- }
- }
- }
- /*cout<<"comp\n";
- cvv(comp);
- cout<<"last comp\n";
- cv(comp[comp.size() - 1]);*/
- sort(vrt.begin(), vrt.end(), cmp);
- int mx_v = vrt[0];
- if (lvl[mx_v] < mx){
- for (int i = 0; i < n; ++i){
- if (vrt[i] == mx_v) continue;
- else if (find(G[mx_v].begin(), G[mx_v].end(), vrt[i]) != G[mx_v].end()) continue;
- else if (lvl[vrt[i]] == mx) continue;
- G[mx_v].push_back(vrt[i]);
- G[vrt[i]].push_back(mx_v);
- lvl[mx_v]++;
- lvl[vrt[i]]++;
- Edge.push_back({min(mx_v, vrt[i]), max(mx_v, vrt[i])});
- if (lvl[mx_v] == mx) {
- break;
- }
- }
- }
- //cout<<"graph\n";
- //cG();
- cEdge();
- }
- /*
- 15 4 3
- 17 7 5
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement