http://acm.hdu.edu.cn/showproblem.php?pid=4781

Assignment For PrincessTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 639    Accepted Submission(s): 196Special Judge

1
6 8

Case #1:
1 2 1
2 3 2
2 4 3
3 4 4
4 5 5
5 6 7
5 1 6
6 1 8
Hint
The restrictions like N >= 10 will be too big for a sample. So the sample is just a simple case for the detailed formats of input and output,
 and it may be helpful for a better understanding. Anyway it won’t appear in actual test cases.
 

题意：

要求构造一张n个点m条有向边的图，满足如下条件：

每对点间最多有一条边；

没有自环；

从任意一点出发，可以到达其他所有点；

m条边的权值为1,2,3,...,m，所有边的权值都不同；

从任意一点出发，最后要回到该点；

所有回路的权值和为3的倍数。

分析:

随便YY下就行了。

先构造1->2->3->4->...->n->1的环，边权依次为1,2,3,4,...,n;然后调整权值为n的边（当然也可已调整其他的边，这里只是为了方便），使得该环的权值和为3的倍数。然后按模3的余数对于剩下的边权分类，对于任意一条边权x，链接u,v两点，满足u->v路径上的边权和y与x对于3同余，比如1->2->3这条路径上的权值和为1+2=3，那么就可以取一条边权为99的边连1->3。

/*
 *
 * Author : fcbruce
 *
 * Time : Mon 06 Oct 2014 05:31:20 PM CST
 *
 */
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cstdlib>
#include <algorithm>
#include <ctime>
#include <cctype>
#include <cmath>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <set>
#define sqr(x) ((x)*(x))
#define LL long long
#define itn int
#define INF 0x3f3f3f3f
#define PI 3.1415926535897932384626
#define eps 1e-10

#ifdef _WIN32
  #define lld "%I64d"
#else
  #define lld "%lld"
#endif

#define maxm 88*88
#define maxn 88 

using namespace std;

struct _edge
{
  int u,v,w;
}edge[maxm];

int a[maxn<<1],s[maxm<<1];
bool vis[maxm];
bool G[maxn][maxn];

int main()
{
#ifdef FCBRUCE
  freopen("/home/fcbruce/code/t","r",stdin);
#endif // FCBRUCE

  int T_T,__=0;
  scanf("%d",&T_T);

  while (T_T--)
  {
    int n,m,cnt=0,last;
    memset(G,0,sizeof G);
    printf("Case #%d:\n",++__);
    scanf("%d%d",&n,&m);
    stack<int> r[3];
    a[0]=0;
    s[0]=0;
    for (int i=1;i<=n;i++)
    {
      a[i]=i;
      s[i]=s[i-1]+a[i];
    }

    memset(vis,0,sizeof vis);

    if (s[n]%3==0)
    {
      last=n;
    }
    else
    {
      if (s[n]%3==1){last=n+2;s[n]+=2;}
      else {last=n+1;s[n]+=1;}
    }

    vis[last]=true;

    for (int i=1;i<=n;i++)
    {
      a[i+n]=a[i];
      s[i]=s[i-1]+a[i];
    }

    for (int i=1;i<n;i++)
    {
      G[i][i+1]=G[i+1][i]=true;
      edge[cnt++]=(_edge){i,i+1,i};
      vis[i]=true;
    }

    edge[cnt++]=(_edge){n,1,last};
    G[n][1]=G[1][n]=true;

    for (int i=1;i<=m;i++)
    {
      if (vis[i]) continue;
      r[i%3].push(i);
    }

    for (int i=1;i<n;i++)
    {
      for (int k=0;k<n-2;k++)
      {
        int j=i+2+k;
        if (j>n) j-=n;
        if (G[i][j] || G[j][i]) continue;
        j=i+2+k;
        int re=s[j-1]-s[i-1];
        if (j>n) j-=n;
        re%=3;
        if (!r[re].empty())
        {
          G[i][j]=G[j][i]=true;
          edge[cnt++]=(_edge){i,j,r[re].top()};
          r[re].pop();
        }
        if (cnt==m) goto ok;
      }
    }
ok:;
   if (cnt<m) puts("-1");
   else
   {
    for (int i=0;i<cnt;i++)
      printf("%d %d %d\n",edge[i].u,edge[i].v,edge[i].w);
   }
      
  }


  return 0;
}

HDU 4781 Assignment For Princess(YY乱搞)