FJNU 1154 Fat Brother And His Love（胖哥与女神）
Time Limit: 2000MS Memory Limit: 257792K
|
【Description】 |
【题目描述】 |
|
As we know, fat Brother and his goddess is in a same city. The city is consist of N locations and the N locations is connected by M roads. Fat Brother has a crush on his goddess, but when he knew that the goddess want to date with other boy, he is reluctant. So he decided to stop their dating, then he go to find a single giant bomb from the warehouse. He can use this giant bomb blew up a road. Fat Brother wondered whether he can separate goddess and other boy by blowing up a road. Fat Brother gives Q questions that each query is given two numbers u and v which means the number of the location of the goddess and the boy. If fat Brother can separate goddess and other boy, output a line “Hei!Hei!Hei!” and a line integer denoting the ways to separate them. If fat Brother can't, output a line “No! I choose to go die!”. You can think the city which Fat Brother, goddess and boys are in is an undirected graph, and the graph is always connected in the beginning. If you can't understand it, you should observate the sample Input and sample Output |
众所周知，胖哥与他的女神同城。这座城市有N个地方被M条路连接。胖哥迷恋着女神，当他知晓女神要和其他男生约会时，他是拒绝的。因此他决定去阻止这一切，接着他在仓库里找了个大炸弹。他可以用这个炸弹破坏一条路。胖哥想知道是否通过破坏一条路阻隔女神与其他男生。胖哥给出Q个问题，每个问题给定两个数u和v表示女神与其男生的位置。如果胖哥可以阻隔女神与其他男生，输出一行“Hei!Hei!Hei!”与一行整数表示将他们分开方式。否则输出一行“No! I choose to go die!”。 你可以认为胖哥所在的城市中，女神与男生在一个无向图中，并且开始时图都是连通的。 如果你还是不明觉厉，可以看看输入输出样例。 |
|
【Input】 |
【输入】 |
|
There are multiple test cases. The first line of input contains an integer T (T <= 25) indicating the number of test cases. For each test case: The first line contains three integer N, M and Q denoting there are N locations and M roads in the city. The Q denoting there are Q questions. (1 <= N <= 100000, 1 <= m <= 100000, 1 <= Q <= 100000) Each of the 2…M + 1 lines contains two integers u and v denoting there is a undirected road between u and v. Each of the M + 2 … M + 1 + Q lines contains two integer u and v denoting the fat Brother's question. |
多组测试用例。 第一行是一个整数T(T <= 25)表示测试用例的数量。对于每个测试用例： 第一行有三个数N, M与Q 表示这个城市有N个地方M条路。Q表示有Q个问题。(1 <= N <= 100000, 1 <= m <= 100000, 1 <= Q <= 100000) 第2…M + 1行每行有两个整数u和v表示u与v间有一条双向的路。 第M + 2 … M + 1 + Q行每行有两个整数u与v，表示胖哥的问题。 |
|
【Output】 |
【输出】 |
|
For each case, output according to Title Description. |
对于每个用例，输出题目描述要求的结果。 |
|
【Sample Input - 输入样例】 |
【Sample Output - 输出样例】 |
|
2 9 11 19 1 2 1 3 2 3 2 4 4 5 4 6 5 6 6 7 7 8 7 9 8 9 1 2 1 3 2 3 2 4 4 5 4 6 5 6 6 7 7 8 7 9 8 9 1 4 4 7 8 5 3 6 9 4 1 6 7 3 2 9 10 9 8 1 2 1 3 3 4 4 5 3 6 6 7 3 8 8 9 8 10 1 5 1 2 7 5 9 4 2 3 6 2 4 1 3 9 |
No! I choose to go die! No! I choose to go die! No! I choose to go die! Hei!Hei!Hei! 1 No! I choose to go die! No! I choose to go die! No! I choose to go die! Hei!Hei!Hei! 1 No! I choose to go die! No! I choose to go die! No! I choose to go die! Hei!Hei!Hei! 1 Hei!Hei!Hei! 1 Hei!Hei!Hei! 1 Hei!Hei!Hei! 1 Hei!Hei!Hei! 1 Hei!Hei!Hei! 1 Hei!Hei!Hei! 2 Hei!Hei!Hei! 2 Hei!Hei!Hei! 3 Hei!Hei!Hei! 1 Hei!Hei!Hei! 4 Hei!Hei!Hei! 3 Hei!Hei!Hei! 2 Hei!Hei!Hei! 3 Hei!Hei!Hei! 2 Hei!Hei!Hei! 2 |
【题解】
2016.10.30补：此代码在
1
3 2 1
1 3
3 2
1 3
时存在问题，测试数据的给出方式似乎恰好回避了访问乱序
实际中的缩点算法存在漏洞，待更新（加个数组就好了，懒癌发作，有空再补）……
题目的大意就是在连通的无向图里面找割边的数量。
大体步骤：①缩点（合并环）Tarjan算法 ②建立多叉树 ③查询
Tarjan算法：百度一下（反正我也看不懂，直接看代码的）
建立多叉树：因为环都没有了，因此图就变成一颗多叉树了
查询：
暴力搜索：因为目测暴力搜索会超时，所以就没去试了（懒癌发作）
树链剖分：根据某人表示可以用，然而本渣并不能看懂……
所以我就看着树链剖分的那幅图，自己琢磨着把树用部分转数组的方式加快
从1开始，把其中一个分枝加入读取行的数组，其他分枝都加入到下一行的数组中去。保存每个元素第一次出现的位置，每次跳转到当前数组开头只需要O(1)，晚建立的层不断向早建立的层调整，可以快速（大雾）得到公共父节点，并且在执行的时候把经过的边数累计，就可以得到割边数量了。
【代码 C++】
#include<cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define mx 100005 struct edge {
int to, next;
}Edge[mx], EdgeOLD[mx << ];
int Head[mx], iE, iE_OLD, ID[mx];
int Stack[mx], iS = ;
bool inUS[mx];
void addEdgeOLD(int u, int v) {
EdgeOLD[iE_OLD].next = Head[u]; EdgeOLD[iE_OLD].to = v;
Head[u] = iE_OLD++;
}
void addEdge(int u, int v) {
Edge[iE].next = Head[u]; Edge[iE].to = v;
Head[u] = iE++;
} void DFS_Tarjan(int now, int anti) {//(当前节点, 反向边)
ID[now] = Stack[++iS] = now;
inUS[now] = ;
int u, v, i = iS;
for (u = Head[now]; ~u; u = EdgeOLD[u].next) {
if (u == anti) continue;
v = EdgeOLD[u].to;
if (!inUS[v]) DFS_Tarjan(v, u ^ );
ID[now] = std::min(ID[now], ID[v]);
}
if (Stack[i] == ID[now]) {
while (i <= iS) {
inUS[Stack[iS]] = ;
ID[Stack[iS--]] = ID[now];
}
}
}
void markID() {
iS = ;
memset(inUS, , sizeof(inUS));
DFS_Tarjan(, -);
} std::vector<int> listTree[mx];
struct Point {
int y, x;
}PointAddress[mx];
void BFS() {
int u, v, y, x, now;
bool fst = ;
std::queue<Point> q;
q.push({ iS = , });
PointAddress[] = { , };
listTree[].push_back();
++inUS[]; while (!q.empty()) {
y = q.front().y; x = q.front().x;
now = listTree[y][x]; q.pop();
fst = ; for (u = Head[now]; ~u; u = Edge[u].next) {
v = Edge[u].to;
if (inUS[v]) continue;
++inUS[v];
if (!fst) {//加入当前行
q.push(PointAddress[v] = { y, listTree[y].size() });
listTree[y].push_back(v); ++fst;
}
else {//加入新一行
listTree[++iS].push_back(now);
q.push(PointAddress[v] = { iS, listTree[iS].size() });
listTree[iS].push_back(v);
}
}
}
}
void buildAddress(int n) {
iE = ;
int HeadOLD[mx], i, u, v;
memcpy(HeadOLD, Head, sizeof(Head));
memset(Head, -, sizeof(Head));
for (i = ; i <= n; ++i) {//建立多叉树
for (u = HeadOLD[i]; ~u; u = EdgeOLD[u].next) {
v = EdgeOLD[u].to;
if (ID[i] < ID[v]) addEdge(ID[i], ID[v]);
}
} for (i = ; i < mx; ++i) listTree[i].clear();
BFS();//将各个节点加入数组
} int fid(Point u, Point v) {
int opt = , to;
Point temp;
while (u.y != v.y) {//未跳转到同一行时进行跳转，并记录经过边的数量。
if (u.y < v.y) { temp = v; v = u; u = temp; }
opt += u.x;
to = listTree[u.y][];
u = PointAddress[to];
}
if (u.x < v.x) { u.x ^= v.x; v.x ^= u.x; u.x ^= v.x; }
return opt + u.x - v.x;
} int main() {
int t, n, m, q, i, u, v;
while (~scanf("%d", &t)) {
while (t--) {
memset(Head, -, sizeof(Head)); iE_OLD = ;
scanf("%d%d%d", &n, &m, &q);
for (i = ; i < m; ++i) {
scanf("%d%d", &u, &v);
addEdgeOLD(u, v); addEdgeOLD(v, u);
}
markID();//对各个顶点进行再编号
buildAddress(n);//建立各顶点的地址
for (i = ; i < q; ++i) {
scanf("%d%d", &u, &v);
u = ID[u]; v = ID[v];
if (u == v) puts("No! I choose to go die!");
else {
puts("Hei!Hei!Hei!");
printf("%d\n", fid(PointAddress[u], PointAddress[v]));
}
}
}
}
return ;
}
FJNU 1154
#include<cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define mx 100005
int readInt() {
int add = getchar() - '';
for (char a = getchar(); a >= '' && a <= ''; a = getchar()) {
add = add * + a - '';
}
return add;
} struct edge {
int to, next;
}Edge[mx], EdgeOLD[mx << ];
int Head[mx], iE, iE_OLD, ID[mx], HeadA[mx];
int Stack[mx], iS = ;
bool inUS[mx];
void addEdgeOLD(int u, int v) {
EdgeOLD[iE_OLD].next = Head[u]; EdgeOLD[iE_OLD].to = v;
Head[u] = iE_OLD++;
}
void addEdge(int u, int v) {
Edge[iE].next = Head[u]; Edge[iE].to = v;
Head[u] = iE++;
} void DFS_Tarjan(int now, int anti) {//(当前节点, 反向边)
ID[now] = Stack[++iS] = now;
inUS[now] = ;
int u, v, i = iS;
for (u = Head[now]; ~u; u = EdgeOLD[u].next) {
if (u == anti) continue;
v = EdgeOLD[u].to;
if (!inUS[v]) DFS_Tarjan(v, u ^ );
ID[now] = std::min(ID[now], ID[v]);
}
if (Stack[i] == ID[now]) {
while (i <= iS) {
inUS[Stack[iS]] = ;
ID[Stack[iS--]] = ID[now];
}
}
}
void markID() {
iS = ;
memset(inUS, , sizeof(inUS));
DFS_Tarjan(, -);
} struct Point {
int y, x, data;
}PointAddress[mx];
void BFS() {
int u, v, y, x, now, HeadASize[mx];
memset(HeadASize, , sizeof(HeadASize));
bool fst = ;
std::queue<Point> q;
q.push({ iS = , , });
PointAddress[] = { , , };
HeadA[] = ; ++HeadASize[];
++inUS[]; while (!q.empty()) {
y = q.front().y; x = q.front().x; now = q.front().data;
q.pop();
fst = ; for (u = Head[now]; ~u; u = Edge[u].next) {
v = Edge[u].to;
if (inUS[v]) continue;
++inUS[v];
if (fst) {//加入当前行
q.push(PointAddress[v] = { y, HeadASize[y]++, v });
fst = ;
}
else {//加入新一行
HeadA[++iS] = now; ++HeadASize[iS];
q.push(PointAddress[v] = { iS, HeadASize[iS]++, v });
}
}
}
}
void buildAddress(int n) {
iE = ;
int HeadOLD[mx], i, u, v;
memcpy(HeadOLD, Head, sizeof(Head));
memset(Head, -, sizeof(Head));
for (i = ; i <= n; ++i) {//建立多叉树
for (u = HeadOLD[i]; ~u; u = EdgeOLD[u].next) {
v = EdgeOLD[u].to;
if (ID[i] < ID[v]) addEdge(ID[i], ID[v]);
}
} BFS();//将各个节点加入数组
}
int fid(Point u, Point v) {
int opt = ;
Point temp;
while (u.y != v.y) {//未跳转到同一行时进行跳转，并记录经过边的数量。
if (u.y < v.y) { temp = v; v = u; u = temp; }
opt += u.x;
u = PointAddress[HeadA[u.y]];
}
if (u.x < v.x) { u.x ^= v.x; v.x ^= u.x; u.x ^= v.x; }
return opt + u.x - v.x;
}
int main() {
int t, n, m, q, i, u, v;
while (t = readInt(), t>) {
while (t--) {
memset(Head, -, sizeof(Head)); iE_OLD = ;
n = readInt(); m = readInt(); q = readInt();
for (i = ; i < m; ++i) {
u = readInt(); v = readInt();
addEdgeOLD(u, v); addEdgeOLD(v, u);
}
markID();//对各个顶点进行再编号
buildAddress(n);//建立各顶点的地址
for (i = ; i < q; ++i) {
u = ID[readInt()]; v = ID[readInt()];
if (u == v) puts("No! I choose to go die!");
else {
puts("Hei!Hei!Hei!");
printf("%d\n", fid(PointAddress[u], PointAddress[v]));
}
}
}
}
return ;
}
【后记】
由于不同平台对栈内存的分配不同，在windows默认1MB的情况下某些数据会出现爆栈的情况（OJ上是linux系统），自己可以提高栈内存的大小。