题目
题意: 给定n个点，每个点有d条有向边，要求构造出c个连通块。
思路:
时间复杂度: O(nd*log(nd))
代码:
#include using namespace std; typedef long long ll; const int N = 1e5+10; int n,m,k,T; int d,c; int a[N]; void solve() { scanf("%d%d%d",&n,&d,&c); ll t = c*(d+1); if(d == 0) { if(n == c) puts("Yes"); else puts("No"); return ; } if(d == 1) { if(n != 2*c) { puts("No"); return ; } puts("Yes"); int cnt = 1; for(int i=1;i<=n;++i) { if(cnt & 1) printf("%d\n",i+1); else printf("%d\n",i-1); cnt++; } return ; } if(t > n || (n&1)&&(d&1) ) { puts("No"); } else { puts("Yes"); if(d % 2 == 0) { int dx; for(int i=0;i<c-1;++i) { dx = i*(d+1)+1; for(int j=0;j<=d;++j) { vector<int> va; int cnt = 0; int k = (j-1+d+1)%(d+1); while(cnt < d/2) { va.push_back(k); k = (k-1+d+1)%(d+1); cnt++; } k = (j+1+d+1)%(d+1); while(cnt--) { va.push_back(k); k = (k+1+d+1) % (d+1); } sort(va.begin(),va.end()); for(auto item:va) printf("%d ",item+dx); puts(""); } } dx = (c-1)*(d+1)+1; int le = n-dx+1; for(int i=0;i<le;++i) { vector<int> va; int cnt = 0; int k = (i-1+le)%(le); while(cnt < d/2) { va.push_back(k); k = (k-1+le)%(le); cnt++; } k = (i+1+le)%(le); while(cnt--) { va.push_back(k); k = (k+1+le) % (le); } sort(va.begin(),va.end()); for(auto item:va) printf("%d ",item+dx); puts(""); } } else { int dx; for(int i=0;i<c-1;++i) { dx = i*(d+1)+1; for(int j=0;j<=d;++j) { vector<int> va; int cnt = 0; int k = (j-1+d+1)%(d+1); while(cnt < d/2) { va.push_back(k); k = (k-1+d+1)%(d+1); cnt++; } k = (j+1+d+1)%(d+1); while(cnt--) { va.push_back(k); k = (k+1+d+1) % (d+1); } if(j <= d/2) va.push_back(j+1+d/2); else va.push_back(j-1-d/2); sort(va.begin(),va.end()); for(auto item:va) printf("%d ",item+dx); puts(""); } } dx = (c-1)*(d+1)+1; int le = n-dx+1; for(int i=0;i<le;++i) { vector<int> va; int cnt = 0; int k = (i-1+le)%(le); while(cnt < d/2) { va.push_back(k); k = (k-1+le)%(le); cnt++; } k = (i+1+le)%(le); while(cnt--) { va.push_back(k); k = (k+1+le) % (le); } sort(va.begin(),va.end()); if(i <= (le-1)/2) va.push_back(i+1+(le-1)/2); else va.push_back(i-1-(le-1)/2); sort(va.begin(),va.end()); for(auto item:va) printf("%d ",item+dx); puts(""); } } } } signed main(void) { solve(); return 0; }
