hdu4781Assignment For Princess（2013 成都）构造题 - c++编程基础

首先所有回路的边值和都为%3==0,至少有一个回路

则先构造一个大的回路，将所有的点包含在内，n点，n边，由于n+3<=m,必定可以构造出来，此时此图是满足要求的

然后再此图的基础上加边，并保证仍然满足要求即可。若找不到给定值的边，则print-1

ps：

（1）题目10 <= N <= 80, N+3 <= M <= N2/7

可是却给了个n=6，m=8的样例，明显错误的

（2）sum+i%3==0出错了，（sum+i）% 3 == 0，加括号才行

//#pragma comment(linker, "/STACK:1024000000,1024000000")  
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
using namespace std;  
  
#define FF(i, a, b) for(int i = (a); i < (b); ++i)  
#define FE(i, a, b) for(int i = (a); i <= (b); ++i)  
#define FD(i, b, a) for(int i = (b); i >= (a); --i)  
#define REP(i, N) for(int i = 0; i < (N); ++i)  
#define CLR(a, v) memset(a, v, sizeof(a))  
#define PB push_back  
#define MP make_pair  
  
typedef long long LL;  
const int INF = 0x3f3f3f3f;  
const int maxn = 100;  
  
int n, m;  
int dis[maxn][maxn], g[maxn][maxn];  
vector >E[maxn];  
bool vis[maxn * maxn];  
  
int dfs(int u, int pos, int fa, int val)  
{  
    if (u == pos) return val;  
    REP(r, E[u].size())  
    {  
        int v = E[u][r].first, d = E[u][r].second;  
        if (v != fa) return dfs(v, pos, u, val + d);  
    }  
}  
  
void pre()  
{  
    FE(i, 1, n) FE(j, 1, n)  
        g[i][j] = dfs(i, j, -1, 0);  
}  
  
bool check(int x)  
{  
    FE(i, 1, n) FE(j, 1, n)  
    {  
        if (i != j)  
        if (!dis[i][j] && !dis[j][i] && g[i][j] % 3 == x % 3)  
        {  
            dis[i][j] = x;  
            return true;  
        }  
    }  
    return false;  
}  
  
bool solve()  
{  
    FE(i, 1, m)  
    {  
        if (!vis[i] && !check(i))  
            return false;  
    }  
    return true;  
}  
  
int main ()  
{  
    int T;  
    scanf("%d",&T);  
    int nc = 1;  
    while (T--)  
    {  
        scanf("%d%d", &n, &m);  
        CLR(vis, 0);  
        CLR(dis, 0);  
        REP(i, maxn) E[i].clear();  
        int sum = 0;  
        FE(i, 1, n - 1)  
        {  
            vis[i] = 1;  
            E[i].PB(MP(i + 1, i));  
            dis[i][i + 1] = i;  
            sum += i;  
        }  
        FE(i, n, n + 3)  
        {  
            if (!vis[i] && sum + i % 3 == 0)  
            {  
                vis[i] = 1;  
                E[n].PB(MP(1, i));  
                dis[n][1] = i;  
                break;  
            }  
        }  
        pre();  
        printf("Case #%d:\n", nc++);  
        if (solve())  
        {  
            FE(i, 1, n) FE(j, 1, n)  
            {  
                if (dis[i][j])  
                {  
                    printf("%d %d %d\n", i, j, dis[i][j]);  
                }  
            }  
        }  
        else printf("-1\n");  
    }  
    return 0;  
}