首页 > 代码库 > HDOJ--4781--Assignment For Princess【构造有向图】

HDOJ--4781--Assignment For Princess【构造有向图】

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

题意:给你两个数,n代表顶点个数,m代表边数,要你建一个图,要求:

1. 有向图,且两个点之间最多只有一条边。

2. 边的权值大小为1~m,每个值只能用一次。

3. 任意一个点都可以到达其余各个顶点。

4. 任意一个环的边上权值之和是3的倍数。

5. 不存在自身环。


思路:先从1顶点到n,相邻两个顶点构造一条有向边,权值分别是1、2、3……n-1,n到1也连一条边,取n、n+1或n+2,取满足权值和是3的倍数的那个值,这样这n个顶点就构成了一个大环,并且满足权值和是3的倍数,因为m的取值最小是n+3,所以这个大环一定能构造出。

对于剩下的m-n条边,假设一条权值为x的有向边要连接u、v两个顶点,则x%3和u、v两顶点间边的权值和sum%3相等才能满足题目要求,如下图所示

顶点{1,2,3,4}是一个环,边的权值和是3的倍数,顶点{1,2,4}也是个环,边的权值和也是3的倍数,因为edge[2][4]替换了edge[2][3]+edge[3][4],只有它们的权值模3相等时才能满足新的环的权值和也是3的倍数。

由于我们构造大环是从小到大构造的,所以添加剩下的m-n条边的时候,边也应该从顶点下标小的点到顶点下标大的点,因为这是有向图,只有这样环才正确。如果图中顶点2、顶点4之间的边是从4到2,虽然(edge[2][4]%3)==(edge[2][3]+edge[3][4])%3,但此时{2,3,4}形成了一个环,显然边的权值和不是3的倍数。

不过经过我测试,这题数据不严谨。就算方向不是从顶点下标小的到顶点下标大的,也能AC


#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 110
#define eps 1e-7
#define INF 0x7FFFFFFF
#define seed 131
#define ll long long
#define ull unsigned long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

struct node{
    int u,v,dis;
}edge[10000];
int vis[10000],mapp[90][90],sum[90];
int n,m,cnt,flag;
void gao(int x){
    int i,j;
    for(i=1;i<=n;i++){
        for(j=i+1;j<=n;j++){
            if(!mapp[i][j]&&!mapp[j][i]){
                if((sum[j]-sum[i]+3)%3==x%3){
                    edge[cnt].u = i;
                    edge[cnt].v = j;
                    edge[cnt].dis = x;
                    cnt++;
                    mapp[i][j] = 1;
                    vis[x] = 1;
                    return ;
                }
            }
        }
    }
    flag = 1;
}
int main(){
    int t,i,j,k=1;
    scanf("%d",&t);
    while(t--){
        memset(mapp,0,sizeof(mapp));
        memset(sum,0,sizeof(sum));
        memset(vis,0,sizeof(vis));
        cnt = 0;
        flag = 0;
        int tot = 0;
        scanf("%d%d",&n,&m);
        for(i=1;i<n;i++){
            tot += i;
            edge[cnt].u = i;
            edge[cnt].v = i+1;
            edge[cnt].dis = i;
            vis[i] = 1;
            mapp[i][i+1] = 1;
            cnt++;
            sum[i] = (sum[i-1] + i - 1) % 3;
        }
        edge[cnt].u = n;
        edge[cnt].v = 1;
        if((tot+n)%3==0)    tot = n;
        else if((tot+n+1)%3==0) tot = n + 1;
        else    tot = n + 2;
        edge[cnt].dis = tot;
        vis[tot] = 1;
        mapp[n][1] = 1;
        cnt++;
        sum[n] = (sum[n-1] + n - 1) % 3;
        for(i=1;i<=m;i++){
            if(!vis[i]){
                gao(i);
            }
            if(flag)    break;
        }
        printf("Case #%d:\n",k++);
        if(flag){
            puts("-1");
            continue;
        }
        for(i=0;i<m;i++){
            printf("%d %d %d\n",edge[i].u,edge[i].v,edge[i].dis);
        }
    }
    return 0;
}