本文共 1473 字，大约阅读时间需要 4 分钟。
题意：
给你一个数k，用n个点画出k个长度为3的环，然后输出n的个数以及图的矩阵表示，mat[i][j] = 0表示无边 1表示有边。
思路：
如果存在n点的话，则最多能够组合出的长度为3的环有c(n,3)个，当然这些特定的数，不能把k，全部表示出来，我们首先找出C(i,3)<=k的最大的i，然后不断往里面添加点，当我们添加一个点之后，我们可以从已有的图形里面的i个点里面选出2两个与刚加入的节点构成三元环，就这样枚举直到满足k个。
#include #include #include #include #include #include #include #include #include #include #define CL(a,num) memset((a),(num),sizeof(a))#define iabs(x) ((x) > 0 ? (x) : -(x))#define Min(a,b) (a) > (b)? (b):(a)#define Max(a,b) (a) > (b)? (a):(b)#define ll long long#define inf 0x7f7f7f7f#define MOD 1073741824#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define test puts("<------------------->")#define maxn 100007#define M 1000007#define N 107using namespace std;//freopen("data.in","r",stdin);int mat[N][N];int main(){ int k,i,j,ki; while (~scanf("%d",&k)){ CL(mat,0); //首先找出小于等于k的最多的节点数i for (i = 3; i <= 100; ++i){ if (i*(i - 1)*(i - 2)/6 > k) break; } i--; k = k - i*(i - 1)*(i -2)/6; //更新临界矩阵 for (j = 1; j <= i; ++j){ for (ki = 1; ki <= i; ++ki){ mat[j][ki] = (j != ki)*1; } } //printf(">>>%d %d\n",i,k); //逐渐加边，枚举增加的三元环 while (k > 0){ for (j = 2; j <= i; ++j){ if (j*(j - 1)/2 > k) break; } j--; i++;//i++是新加入的节点 for (ki = 1; ki <= j; ++ki) mat[i][ki] = mat[ki][i] = 1; k -= (j*(j - 1)/2); } k = i; printf("%d\n",k); for (i = 1; i <=k ; ++i){ for (j = 1; j <= k; ++j) printf("%d",mat[i][j]); printf("\n"); } } return 0;}
转载地址：http://ybwua.baihongyu.com/
View Code