如题,萌新一枚,用对偶图做P4646,代码如下
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int n, w, a_cnt;
int depth[100005] = {0}, nbrs[100005] = {0}; //"a_cnt" is count of areas
int ans[100005], k = 0;
vector<int> nbr[100005]; //"nbr" represents neighbor
bool vis[100005] = {0};
struct point_ {
int x = -1, y = -1;
int walls[4] = {0};
} point[100005];
struct wall_ {
int start = 0, end = 0, area = 0;
short dir = -1;
} wall[400005];
queue<int> q;
void input () {
cin >> n;
for (int i=1; i<=n; ++i)
cin >> point[i].x >> point[i].y;
cin >> w;
for (int i=1; i<=w; ++i) {
cin >> wall[i].start >> wall[i].end;
wall[w+i].start = wall[i].end;
wall[w+i].end = wall[i].start;
}
for (int i=1; i<=2*w; ++i) {
if (point[wall[i].start].x == point[wall[i].end].x)
wall[i].dir = 2 * (point[wall[i].start].y > point[wall[i].end].y);
if (point[wall[i].start].y == point[wall[i].end].y)
wall[i].dir = 2 * (point[wall[i].start].x < point[wall[i].end].x) + 1;
point[wall[i].start].walls[wall[i].dir] = i;
}
return;
}
int find_area () {
for (int i=1; i<=2*w; ++i) {
if (wall[i].area) continue;
wall[i].area = ++a_cnt;
int now_ = i;
while (true) {
int next_ = 0, reverse_dir;
for (int j=1; j<=4; ++j) {
if (next_) continue;
reverse_dir = wall[now_].dir>=2 ? (wall[now_].dir-2) : (wall[now_].dir+2);
next_ = point[wall[now_].end].walls[(j+reverse_dir)%4];
}
now_ = next_;
if (now_ == i) break;
wall[now_].area = a_cnt;
}
}
int min_y = 2147483647, min_yx = 2147483647, min_p;
for (int i=1; i<=n; ++i)
if (point[i].y <= min_y) {
if (point[i].y < min_y)
min_yx = 2147483647;
min_y = point[i].y;
if (point[i].x <= min_yx) {
min_yx = point[i].x;
min_p = i;
}
}
return min_p;
}
void build () {
for (int i=1; i<=w; ++i)
if (wall[i].area != wall[i+w].area) {
nbr[wall[i].area].push_back (wall[i+w].area);
nbrs[wall[i].area]++;
}
return;
}
void bfs () {
int start_area = find_area ();
build ();
q.push (start_area);
vis[start_area] = 1;
while (!q.empty ()) {
int now_area = q.front ();
q.pop ();
for (int i=1; i<=nbrs[now_area]; ++i)
if (!vis[nbr[now_area][i]]) {
vis[nbr[now_area][i]] = 1;
q.push (nbr[now_area][i]);
depth[nbr[now_area][i]] = depth[now_area] + 1;
}
}
return;
}
void print () {
for (int i=1; i<=w; ++i)
if (depth[wall[i].area] == depth[wall[i+w].area])
ans[++k] = i;
cout << k << endl;
for (int i=1; i<=k; ++i)
cout << ans[i] << endl;
return;
}
int main () {
ios::sync_with_stdio (false);
cin.tie (0);
input ();
bfs ();
print ();
return 0;
}
代码交上去之后显示CE“编译错误”但不显示错误原因 求助