# TC SRM566 DIV1 250 PenguinSledding

## 题目描述

#### En

Percy is a penguin in charge of the greatest penguin pastime, penguin sledding. It is Percy’s job to help design the sledding course. Percy is a very careful penguin and would like to set up the course in a way that no two sledding paths cross.

The sledding course contains some significant locations called checkpoints, and some sledding paths. The checkpoints are numbered 1 through numCheckpoints, inclusive. Each sledding path is a straight line segment that connects two distinct checkpoints. The checkpoints are distinct, and no three of them lie on the same line. (Therefore, no checkpoint will ever lie on a sledding path.)

When designing the course, Percy specifies some pairs of checkpoints that will be connected by sledding paths. Accidents happen when two sledding paths cross, so such designs should be avoided. Unfortunately, Percy does not know the precise locations of all checkpoints. Therefore, Percy’s design must not allow two sledding paths to cross, regardless of the locations of the checkpoints. Percy calls a design safe if he is sure that no two sledding paths will cross.

Percy just found an old design that may be unsafe. He would like to change it to a safe design by removing zero or more sledding paths from the original design. Count all different safe designs he may obtain from the old design in this way. Two designs are considered different if there is a pair of checkpoints that is connected by a sledding path in one design and disconnected in the other.

You are given the int numCheckpoints representing the number of checkpoints in the old design. You are also given two vector s checkpoint1 and checkpoint2 that describe the sledding paths in the old design: For each i, there is a sledding path connecting the checkpoints checkpoint1[i] and checkpoint2[i]. Return the number of safe designs that can be made from the old design.

### 数据范围

• numCheckpoints will be between 2 and 50, inclusive.
• checkpoint1 will contain between 1 and 50 elements, inclusive.
• checkpoint1 and checkpoint2 will contain the same number of elements.
• Each element of checkpoint1 will be between 1 and numCheckpoints, inclusive.
• Each element of checkpoint2 will be between 1 and numCheckpoints, inclusive.
• Each pair of checkpoints will be connected by at most one sledding path.
• For each i, element i of checkpoint1 will not be equal to element i of checkpoint2.

## 参考程序

using namespace std;
typedef long long LL;
const int ArSize = 55;
bool A[ArSize][ArSize];
int dgr[ArSize], fa[ArSize];

class PenguinSledding {
public:
LL countDesigns( int numCheckpoints, vector <int> checkpoint1, vector <int> checkpoint2 );
private:
void add_edge(int u, int v) {
int fa1 = find(u), fa2 = find(v);
if (fa1 != fa2) fa[fa1] = fa2;
A[u][v] = A[v][u] = true, ++dgr[u], ++dgr[v];
}
LL fast_pow(LL bs, int ex) {
LL res = 1;
for (; ex; ex >>= 1, bs *= bs) if (ex & 1) res *= bs;
return res;
}
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
};

LL PenguinSledding::countDesigns(int numCheckpoints, vector <int> checkpoint1, vector <int> checkpoint2) {
memset(A, 0, sizeof(A));    // A是邻接矩阵
memset(dgr, 0, sizeof(dgr));    // dgr是每个点的度数
for (int i = 1; i <= numCheckpoints; i++) fa[i] = i;    // emmm这个并查集好像没什么用
for (int i = 0, lim = checkpoint1.size(); i < lim; i++) add_edge(checkpoint1[i], checkpoint2[i]);
LL res = 0;
for (int i = 1; i <= numCheckpoints; i++) res += fast_pow(2, dgr[i]) - 1;   // 这里先排除没有边的情况
for (int i = 1; i <= numCheckpoints; i++)
for (int j = i + 1; j <= numCheckpoints; j++)
if (A[i][j])
for (int k = j + 1; k <= numCheckpoints; k++)
if (A[i][k] && A[j][k]) ++res;  // 计算三角形个数
return res - checkpoint1.size() + 1;    // 减去一条边重复计算的次数，再加上一个没有边的情况
}