首页 > 代码库 > hdu4781 Assignment For Princess（构造）
hdu4781 Assignment For Princess（构造）
题目链接：hdu4781 Assignment For Princess
题意：n个点m条边，每条有向边的权值分别是1,2,3…m，一个点能到达任意一个点，没有重边和自环，没有任何两条边的权值相同，任意一个有向环的权值和必须是3的倍数，现在需要把这个图输出来。
题解：注意到题目给出的范围m >= n+3，所以一定是可以构造出一个1~n的回路使得权值和为3的倍数的，可以让前n-1条边权值为1~n-1，第n条边（n->1）可以为n, n+1, n+2从而满足题意，后面再连任意两条不相邻的边时，边权模3的大小和原来构造出的第一条回路中两条边的距离大小相等即可。
第一遍自己做没构造成功（失败的代码太丑就不贴了orz），后来参考了这个博客：http://blog.csdn.net/cevaac/article/details/41007703
感觉这类题挺有趣的，我还差得远，加油呐！
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<cmath> 5 #define CLR(a,b) memset((a),(b),sizeof((a))) 6 using namespace std; 7 8 const int inf = 0x3f3f3f3f; 9 const int mod = 1e9 + 7;10 const int N = 101;11 const int M = 1001;12 int n, m;13 int g[M][3];14 int cnt[3];//边权值模3为0,1,2的个数15 int d[M];//顶点i到1的距离（1~n构造第一个回路）16 int main(){17 int t, i, j, k, x, p;18 scanf("%d", &t);19 for(k = 1; k <= t; ++k){20 printf("Case #%d:\n", k);21 CLR(d, 0);22 CLR(cnt, 0);23 scanf("%d%d", &n, &m);24 for(i = 1; i <= n-1; ++i){//前n-1条边权为1...n-125 printf("%d %d %d\n", i, i+1, i);26 d[i+1] = d[i] + i;27 }28 for(i = n; i <= m; ++i){29 x = i % 3;30 cnt[x]++;31 g[cnt[x]][x] = i;32 }33 p = (3 - d[n]%3) %3;//满足构造出的第一个回路权值和为3的倍数34 printf("%d 1 %d\n", n, g[cnt[p]--][p]);35 for(i = 1; i <= n-2; ++i){36 for(j = i+2; j <= n; ++j){37 if(i == 1 && j == n)38 continue;39 p = (d[j] - d[i]) % 3;40 if(cnt[p])41 printf("%d %d %d\n", i, j, g[cnt[p]--][p]);42 }43 }44 }45 return 0;46 }
hdu4781 Assignment For Princess（构造）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。