题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5302
题意：给你一个无向图，它的边要么是黑色要么是白色，且图上的每个点最多与两个黑边两个白边相连。现在，Demon将图分成两部分，一部分包含所有的黑边，另一部分包括所有的白边，给你白边图中度为0的点的数量w0，度为1的点数w1，度为2的点数w2，与黑边图中度为0的点数b1，度为1的点数b1，度为2的点数b2，要你输出任意一个符合条件的原图，如果不能，输出-1
（注1：无论是黑边图，还是白边图，给出的度为0、1、2三种点的数量均>=1；
注2：w0+w1+w2==b0+b1+b2，输出图的点数最多为w0+w1+w2个；
注3：图中无重边，无自环；
解：构造题
考虑每条边对应两度，那么w1或b1为奇数一定无解
排除以上情况，有w1>=2 && b1>=2，将二度的点排成一排，顺次链接起来，然后将首尾分别和一个一度点相连，剩下的一度点两两互相连接即可
这样我们就可以解决黑图或白图，考虑上述构造方法每个点只和相邻的点连接，我们在构造完一图之后，另外一图只需要稍微打乱下点的顺序即可
for example：
1 2 3 4 5 -> 1 4 2 5 3
另外n==4的时候需要特判一下。。。
/*
* Problem: hdu5302 Connect the Graph
* Author: SHJWUDP
* Created Time: 2015/8/10 星期一 19:24:32
* File Name: 1006.cpp
* State: Accepted
* Memo: 构造
*/
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm> using namespace std; int main() {
#ifndef ONLINE_JUDGE
freopen("in", "r", stdin);
//freopen("out", "w", stdout);
#endif
int T;
scanf("%d", &T);
while(T--) {
vector<int> w(), b();
for(int i=; i<; i++) scanf("%d", &w[i]);
for(int i=; i<; i++) scanf("%d", &b[i]);
if((w[] & ) || (b[] & )) {
puts("-1"); continue;
}
int n=w[]+w[]+w[];
if(n<=) {
puts("4\n1 2 0\n1 3 0\n2 3 1\n3 4 1"); continue;
}
int m1=w[]+w[]/;
int m2=b[]+b[]/;
printf("%d\n", m1+m2);
int nw=;
w[]++;
while(w[]--) {
printf("%d %d 0\n", nw, nw+); nw++;
}
w[]-=; nw++;
while(w[]) {
printf("%d %d 0\n", nw, nw+); nw+=;
w[]-=;
}
vector<int> table(n+);
int pos=;
for(int i=; i<=n; i+=) table[pos++]=i;
for(int i=; i<=n; i+=) table[pos++]=i;
int nb=;
b[]++;
while(b[]--) {
printf("%d %d 1\n", table[nb], table[nb+]); nb++;
}
b[]-=; nb++;
while(b[]) {
printf("%d %d 1\n", table[nb], table[nb+]); nb+=;
b[]-=;
}
}
return ;
}
hdu5302