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 8HintThe 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条边的有向图，每条边的权值分别为1，2，3........m,让你构
造满足下列条件的有向图。
1：每两个点之间最多只有一条有向边，且不存在自环。
2：从任意点出发都可以达到其他任意一个点，包括自己。
3：任意一个有向环的权值和都是3的倍数。
思路： 首先我们可以将点1到n连成一条链，边的权值分别是1到n-1，然后点n到点1连
一条边，若n%3为0或2，则边权值为n，否则边权值为n+2（m>=n+3），现在我们构造
出了一个环且满足上述三个条件。那么接下来如何构造剩下的m-n条边呢？
现在我们不管怎么构造都满足第二个条件了，而且现在每个点到自己的距离都是3的倍
数。那么如果我要在u，v两点之间连一条全值为len的边，那么只要满足len%3==dist[u][v]%3即
可（dist表示原环中两个点之间的距离），然后在构造的时候还要注意不要违背第一个条件，所
以我们可以用G[i][j]来表示i，j之间是否右边，如果按这样构造无法构造出图，则无解。
如图 : 要在点2与点4之间加一条权值为 len 的有向边 ，因为
( dist[2][4]+dist[4][2] ) % 3 = 0 , 加的权值为 len 的边要满足
（dist[4][2] + len）% 3 = 0 。有上述两式说明加的边的权值
只要满足len % 3==dist[2][4]%3 (因为是有向边，所以dist[2][4]！=dist[4][2] )。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int inf=999999999;
const int M=7000;
const int maxn=95;
struct node
{
int u,v,val;
node() {}
node(int _u,int _v,int _val):u(_u),v(_v),val(_val) {}
} a[M];
int dis[maxn][maxn],cnt,n,m;
bool G[maxn][maxn],visited[M];
void initial()
{
cnt=0;
memset(G,0,sizeof(G));
memset(visited,0,sizeof(visited));
for(int i=0; i<maxn; i++)
for(int j=0; j<maxn; j++)
{
if(i==j) dis[i][j]=0;
else dis[i][j]=inf;
}
}
void input()
{
scanf("%d %d",&n,&m);
}
void ready()
{
int t;
for(int i=1; i<n; i++)
{
a[cnt++]=node(i,i+1,i);
dis[i][i+1]=i;
G[i][i+1]=1;
visited[i]=1;
}
if(n%3==1) t=n+2;
else t=n;
a[cnt++]=node(n,1,t);
dis[n][1]=t;
visited[t]=1;
G[n][1]=1;
}
void floyd()
{
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
bool judge(int len)
{
int tmp=len%3;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
{
if(i!=j && !G[i][j] && !G[j][i])
{
if(dis[i][j]%3==tmp)
{
a[cnt++]=node(i,j,len);
visited[len]=1;
G[i][j]=1;
return true;
}
}
}
return false;
}
void solve(int co)
{
floyd();
printf("Case #%d:\n",co);
for(int i=1; i<=m; i++)
if(!visited[i])
if(!judge(i))
{
printf("-1\n");
return ;
}
for(int i=0;i<cnt;i++) printf("%d %d %d\n",a[i].u,a[i].v,a[i].val);
}
int main()
{
int T;
scanf("%d",&T);
for(int co=1; co<=T; co++)
{
initial();
input();
ready();
solve(co);
}
return 0;
}
hdu 4781 Assignment For Princess（构造法）
原文：http://blog.csdn.net/u012596172/article/details/43196111