题目链接：这里 题意：构造一个n个点，m条有向边的图，需要满足两个要求： 1.任意一对点对之间最多有一条有向边，且没有自环。 2.保证图联通，m条边的边权严格属于[1, m]且互不相同，从任意点出发，经过任意路径后回到起始点，经过的边权总和是3的倍数。 解法：构造好题，方法 对于每个点i < n构造出i~i+1权值为i的边，用n~1调整权值构造出环，然后其余权值为w的边在i~j且i~j权值与w对3同余的路径上添加。
//HDU 4781 #include <bits/stdc++.h> using namespace std; const int maxn = 6500; int cnt[4]; //记录模3系权值的出现次数 int f[maxn][4]; //f[i][j]，权值为j,的边有哪些 int sum[maxn]; int main() { int T, ks = 0, n, m; scanf("%d", &T); while(T--){ scanf("%d%d", &n, &m); printf("Case #%d:\n", ++ks); memset(cnt, 0, sizeof(cnt)); memset(f, 0, sizeof(f)); //先n个点构成1个环 for(int i = 1; i < n; i++){ printf("%d %d %d\n", i, i + 1, i); sum[i + 1] = sum[i] + i; } for(int i = n; i <= m; i++){ int x = i%3; f[++cnt[x]][x] = i; } int lastedge = (3 - (sum[n] - sum[1]) % 3) % 3; printf("%d 1 %d\n", n, f[cnt[lastedge]--][lastedge]); //构造剩下的n - m条边 for(int i = 1; i <= n - 2; i++){ for(int j = i + 2; j <= n; j++){ if(i == 1 && j == n) continue; int curedge = (sum[j] - sum[i] + 3) % 3; if(cnt[curedge]){ printf("%d %d %d\n", i, j, f[cnt[curedge]--][curedge]); } } } } return 0; }