题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4781
题目大意：给你n个点m条边，要求你构造一个符合条件的有向联通图（若无法构造输出-1，否则输出任意一种方法）
条件：1.任意两点间只有1条边，且不存在自环，每条边的权值均不相等大小为1~m中的值
2.从任一点出发可达其他任何一点且可以回到起点
3.任意一个有向环权值和%3==0
构造方法：可以先构造一个大环1->2->3->4……->n->1,其中1~n中的每条边权值可以为当前点的序号，可以保证1~n的所有数均被取完
而n->1的权值则要看前面的所有边的权值和（因为必须满足有向环权值和%3==0），所以当n%3==1时边权值为n+2，否则为n（不懂自己画个图就懂了）
然后枚举n~m中没有使用过的权值对边进行枚举判断，可行加入答案集，否则输出-1
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <cstring> #include <stack> #include <queue> #include <string> #include <vector> #include <set> #include <map> #include <climits> #define lson root<<1,l,mid #define rson root<<1|1,mid+1,r #define fi first #define se second #define ping(x,y) ((x-y)*(x-y)) using namespace std; #define gamma 0.5772156649015328606065120 //欧拉常数 #define MOD 1000000007 #define inf 0x3f3f3f3f #define N 10100000 #define maxn 1000100 typedef long long LL; typedef pair<int,int> PII; class Node{ public: int x,y,v; Node(){} void t(int _x,int _y,int _v){ x=_x;y=_y;v=_v; } }node; int n,m,d[100][100],vis[1000]; vector<Node>V; //答案集合 void init() { memset(d,0,sizeof(d)); memset(vis,0,sizeof(vis)); //标记权值是否被访问的数组 V.clear(); } bool add(int &v) { for(int i=1; i<=n; ++i) for(int j=i+1; j<=n; ++j) if(!d[i][j]&&(3-(i+j-1)*(j-i)/2%3)%3==v%3) //这条语句是精髓 (i+j-1)*(j-i)/2%3 它表示从i到j的权值和%3的值 { //再用3去减得到的值表示需要加入余数为3-(i+j-1)*(j-i)/2%3)%3的边才满足条件3 node.t(j,i,v); V.push_back(node); d[i][j]=v; vis[v]=1; return true; } return false; } int main() { int i,j,group,_max,Case=0,tv; scanf("%d",&group); while(group--){ scanf("%d%d",&n,&m); init(); for(i=1; i<n; ++i) { d[i][i+1]=i; node.t(i,i+1,i); V.push_back(node); vis[i]=1; } if(n%3==1) i+=2; vis[i]=1; d[1][n]=i; node.t(n,1,i); V.push_back(node); bool flag=true; for(i=n; i<=m&&flag; ++i) if(!vis[i]) flag=add(i); printf("Case #%d: ",++Case); if(!flag){ puts("-1"); continue; } for(i=0; i<m; ++i) printf("%d %d %d ",V[i].x,V[i].y,V[i].v); } return 0; }
这道题也是咨询了北邮的巨巨之后才理解了的，再次感谢他的帮助.