2022牛客多校三_F

2022牛客多校三

传送门

为什么题越补越多了a

F- Fief

prob. : 给n个点m边，两个标记点，问是否存在一个排列使得两个标记点（x，y）在两端，且在该排列中任意划分，分出的两部分仍连通。

ideas:

如果x或y为割点，则不可行（可以画一下图理解一下）

如果有一个环，环内点两两可达，这些点等价

点双缩点后的图，如果是一条链，且xy在链的两端则可行；如果是树则不可行（在任意一个度数>2的节点都会出现决策问题）

---

点双边双参考：https://blog.csdn.net/a_forever_dream/article/details/103019013

点双连通： 对于一个无向图，不包含割点

除了比较特殊的一个点双，其他都满足，任意两点之间存在至少两条点不重复的路径

边双连通: 对于一个无向图，不包含割边

对于一个边双中的任意两个点，它们之间都有至少两条边不重复的路径。

• 点双连通：删掉一个点之后，图仍联通
• 边双连通：删掉一条边之后，图仍联通

点双形象化的理解：

https://www.cnblogs.com/cutemush/p/12686604.html

会以割点为界分割连通块，对于每个连通块标号当做一个新的点；对于割点再单独拎出来当做一个新的点

点双缩点板子：https://blog.csdn.net/qq_41661919/article/details/85482289

但是前向星（

---

真的借这个题学了下点双，板子其实还好，刚开始没理解就上就有点难改了（

注意点开两倍，点双缩点会越缩越多来着（

code:

#include 

#define ll long long
using namespace std;
const int N = 2e5 + 10;
const int M = N << 2;
int head[N];
int ver[M];
int Next[M];
int tot, n, m;

void add(int x, int y) {
    ver[++tot] = y;
    Next[tot] = head[x];
    head[x] = tot;
}

int root;
vector<int> dcc[N];
int stackk[N];
int dfn[N], low[N];
int num = 0;//时间戳
int top;//stackk
int cnt = 0;//联通块数目
bool cut[N];//割点判断
void tarjan(int x) {
    dfn[x] = low[x] = ++num;
    stackk[++top] = x;
    if (x == root && head[x] == 0) {
        dcc[++cnt].push_back(x);//cnt联通块标号
        return;
    }
    int flag = 0;
    for (int i = head[x]; i; i = Next[i]) {
        int y = ver[i];
        if (!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
            if (low[y] >= dfn[x]) {
                flag++;
                if (x != root || flag > 1)cut[x] = true;
                cnt++;
                int z;
                do//弹出的元素与x一起构成一个联通块(或者说割点的子树中的节点+割点?)
                {
                    z = stackk[top--];
                    dcc[cnt].push_back(z);
                } while (z != y);
                dcc[cnt].push_back(x);
            }
        } else low[x] = min(low[x], dfn[y]);
    }
}

int tot2 = 1;
int new_id[N];

int hc[N];
int vc[M];
int nc[M];

int du[N];

void add_c(int x, int y) {
    vc[++tot2] = y;
    nc[tot2] = hc[x];
    hc[x] = tot2;
}

bool vis[N];

void dfs(int x, int p) {
    vis[x] = 1;
    for (int i = hc[x]; i; i = nc[i]) {
        int to = vc[i];
        if (to == p) continue;
        if (!vis[to]) {
            dfs(to, x);
        }
    }
}

int main() {

    scanf("%d%d", &n, &m);
    tot = 1;//方便用^运算访问各边的终点
    for (int i = 1; i <= m; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (x == y)continue;
        add(x, y);
        add(y, x);
    }
    for (int i = 1; i <= n; ++i) {
        if (!dfn[i])root = i, tarjan(i);
    }
    //输出割点
    /*for(int i=1;i<=n;++i)
        if(cut[i])printf("%d ",i);*/
    //上面求割点同时求V-DCC
    //下面输出每个联通块中的点
//    for (int i = 1; i <= cnt; ++i) {
//        for (int j = 0; j < dcc[i].size(); ++j)
//            cout << i << " " << dcc[i][j] << endl;
//    }

    //缩点
    tot2 = 1;
    int num2 = cnt;
    for (int i = 1; i <= n; ++i) {
        if (cut[i])new_id[i] = ++num2;//缩点后割点的新编号,相当于每个割点单独作为一个联通块
    }
    for (int i = 1; i <= cnt; ++i) {
        for (int j = 0; j < dcc[i].size(); ++j) {
            int x = dcc[i][j];
            if (cut[x])//一个联通块中有且只有一个割点，通过割点们把这些联通块连接起来;
            {
                add_c(i, new_id[x]);
                add_c(new_id[x], i);
            } else new_id[x] = i;//其余点均只属于一个联通块
        }
    }

    //输出缩点后的图中各点之间的邻接关系，再次注意^符号的使用，i从2开始，每次加2，
    //tot2是边数
//    for (int i = 2; i < tot2; i += 2) {
//        cout << vc[i ^ 1] << "   " << vc[i] << endl;
//    }

    bool flag = 1;
    dfs(1, -1);
    for (int i = 1; i <= num2; ++i) {
        if (!vis[i]) flag = 0;
    }

    // 链的两端
    for (int i = 1; i <= num2; ++i) {
        for (int u = hc[i]; u; u = nc[u]) {
            du[i]++;
        }
    }

    // 判他是不是树
    for (int i = 2; i <= num2; ++i) {
        if (du[i] > 2) flag = 0;
    }

    int q;
    scanf("%d", &q);

    while (q--) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (n == 2) {
            puts("YES");
            continue;
        }
        if (!flag || cut[x] || cut[y]) {
            puts("NO");
            continue;
        }
        if ((du[new_id[x]] == 1 && du[new_id[y]] == 1 && new_id[x] != new_id[y]) || (cnt == 1)) {
            puts("YES");
        } else {
            puts("NO");
        }
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170

G - Geometry

prob. ： 给两个凸包以及凸包的速度，问多久相撞

ideas：

闵可夫斯基和：两个欧几里得空间的点集的和

多用于探究两个或多个凸包的关系，把凸包的关系转化为向量的加减法

算法思路是将两个凸包的边极角排序（将两个有序的凸包的边极角排序，注意起点位置以及可能存在三点共线的情况，在一些题的情况下需要对闵和后的凸包再求一次凸包)

用闵和可以判断凸包是否相交：将一个凸包B按原点对称，之后与凸包A作闵和，得到的新的凸包，判断原点是否在该凸包内

---

该题可以转化为求是否存在$\vec{a}+k\vec{x}=\vec{b}+k\vec{y}$

即求$\vec{a}-\vec{b}=k(\vec{y}-\vec{x})$

$\vec{a}+(-\vec{b})=k(\vec{y}-\vec{x})$

将凸包B按原点对称之后与A作闵和，对于新的凸包枚举每条边与直线的交点算tmpk然后比较得答案

---

这样做没有什么精度问题，本来队友在写二分+二分会被边界数据卡死

卡精度的题最好不要旋转

“0会变成1e-7 然后跳1e9倍就有值了（？”