HDU4781（2013成都站A题）

题目链接：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[][],vis[];

vector<Node>V;     //答案集合

void init()

{

    memset(d,,sizeof(d));

    memset(vis,,sizeof(vis));   //标记权值是否被访问的数组

    V.clear();

}

bool add(int &v)

{

    for(int i=; i<=n; ++i)

        for(int j=i+; j<=n; ++j)

            if(!d[i][j]&&(-(i+j-)*(j-i)/%)%==v%)  //这条语句是精髓   (i+j-1)*(j-i)/2%3  它表示从i到j的权值和%3的值

            {　　　　　　　　　　　　　　　　　　　　　　　　　//再用3去减得到的值表示需要加入余数为3-(i+j-1)*(j-i)/2%3)%的边才满足条件3

                node.t(j,i,v);

                V.push_back(node);

                d[i][j]=v;

                vis[v]=;

                return true;

            }

    return false;

}

int main()

{

    int i,j,group,_max,Case=,tv;

    scanf("%d",&group);

    while(group--){

        scanf("%d%d",&n,&m);

        init();

        for(i=; i<n; ++i)

        {

            d[i][i+]=i;

            node.t(i,i+,i);

            V.push_back(node);

            vis[i]=;

        }

        if(n%==)

            i+=;

        vis[i]=;

        d[][n]=i;

        node.t(n,,i);

        V.push_back(node);

        bool flag=true;

        for(i=n; i<=m&&flag; ++i) if(!vis[i])

            flag=add(i);

        printf("Case #%d:\n",++Case);

        if(!flag){

            puts("-1");

            continue;

        }

        for(i=; i<m; ++i)

            printf("%d %d %d\n",V[i].x,V[i].y,V[i].v);

    }

    return ;

}

这道题也是咨询了北邮的巨巨之后才理解了的，再次感谢他的帮助.

巴特西

HDU4781（2013成都站A题）

最新文章

热门文章