思路：构造，显然是一个蝴蝶形状的图
#include<bits\stdc++.h>
using namespace std;
int main()
{
int n,k,a,b,c,d;
vector<int>g;
scanf("%d%d",&n,&k);
scanf("%d%d%d%d",&a,&b,&c,&d);
if(n==4)
{
puts("-1");
return 0;
}
if (k<=n)
{
puts("-1");
return 0;
}
for (int i = 1;i<=n;i++)
{
if(i==a||i==b||i==c||i==d)
continue;
g.push_back(i);
}
printf("%d %d ",a,c);
for (int i = 0;i<g.size();i++)
printf("%d ",g[i]);
printf("%d %d\n",d,b);
printf("%d %d ",c,a);
for (int i = 0;i<g.size();i++)
printf("%d ",g[i]);
printf("%d %d\n",b,d);
}
Description
Bearland has n cities, numbered 1 through n. Cities are connected via bidirectional roads. Each road connects two distinct cities. No two roads connect the same pair of cities.
Bear Limak was once in a city a and he wanted to go to a city b. There was no direct connection so he decided to take a long walk, visiting each city exactly once. Formally:
On the other day, the similar thing happened. Limak wanted to travel between a city c and a city d. There is no road between
them but there exists a sequence of n distinct cities u1,?u2,?...,?un that u1?=?c, un?=?d and
there is a road between ui and ui?+?1 for .
Also, Limak thinks that there are at most k roads in Bearland. He wonders whether he remembers everything correctly.
Given n, k and four distinct cities a, b, c, d, can you find possible paths (v1,?...,?vn) and (u1,?...,?un) to satisfy all the given conditions? Find any solution or print -1 if it‘s impossible.
Input
The first line of the input contains two integers n and k (4?≤?n?≤?1000, n?-?1?≤?k?≤?2n?-?2) — the number of cities and the maximum allowed number of roads, respectively.
The second line contains four distinct integers a, b, c and d (1?≤?a,?b,?c,?d?≤?n).
Output
Print -1 if it‘s impossible to satisfy all the given conditions. Otherwise, print two lines with paths descriptions. The first of these two lines should contain n distinct integers v1,?v2,?...,?vn where v1?=?a and vn?=?b. The second line should contain n distinct integersu1,?u2,?...,?un where u1?=?c and un?=?d.
Two paths generate at most 2n?-?2 roads: (v1,?v2),?(v2,?v3),?...,?(vn?-?1,?vn),?(u1,?u2),?(u2,?u3),?...,?(un?-?1,?un). Your answer will be considered wrong if contains more than k distinct roads or any other condition breaks. Note that (x,?y) and (y,?x) are the same road.
Sample Input
7 11 2 4 7 3
2 7 1 3 6 5 4 7 1 5 4 6 2 3
1000 999 10 20 30 40
-1
CodeForces 673D Bear and Two Paths（构造）
原文：http://blog.csdn.net/qq_21057881/article/details/51365984