有 n 只猴子,第一只尾巴挂在树上,剩下的 n-1 只,要么被其他的猴子抓住,要么抓住了其他的猴子,要么两者均有。
当然一只猴子最多抓两只另外的猴子,因为只有两只猴爪子嘛。现在给出这 n 只猴子抓与被抓的信息,并且在某个时刻可能某只猴子会放掉它左手或右手的猴子,导致某些猴子落在地上。求每只猴子落地的时间。
题解:
并查集,路径压缩的时候需要对每个点的答案进行一个 min 操作;
- #include < iostream > #include < cstdio > #include < cstdlib > #include < cstring > #include < string > #include < ctime > #include < cmath > #include < set > #include < map > #include < queue > #include < algorithm > #include < iomanip > #include < stack > using namespace std;#define FILE "dealing"#define up(i, j, n) for (int i = (j); i <= (n); i++)#define pii pair < int,
- int > #define LL int#define mem(f, g) memset(f, g, sizeof(f)) namespace IO {
- char buf[1 << 15],
- *fs,
- *ft;
- int gc() {
- return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 15, stdin), fs == ft)) ? -1 : *fs++;
- }
- int read() {
- int ch = gc(),
- f = 0,
- x = 0;
- while (ch < '0' || ch > '9') {
- if (ch == ' - ') f = 1;
- ch = gc();
- }
- while (ch >= '0' && ch <= '9') {
- x = (x << 1) + (x << 3) + ch - '0';
- ch = gc();
- }
- return f ? -x: x;
- }
- int readint() {
- int ch = getchar(),
- f = 0,
- x = 0;
- while (ch < '0' || ch > '9') {
- if (ch == ' - ') f = 1;
- ch = getchar();
- }
- while (ch >= '0' && ch <= '9') {
- x = (x << 1) + (x << 3) + ch - '0';
- ch = getchar();
- }
- return f ? -x: x;
- }
- }
- using namespace IO;
- const int maxn = 401000,
- inf = 100000000;
- int n,
- m,
- M;
- int c[maxn][2],
- ch[maxn][2],
- t[maxn][2],
- r[maxn];
- int x,
- y,
- fa[maxn],
- ans[maxn];
- pii getfa(int x) {
- if (fa[x] == x) return make_pair(x, ans[x]);
- pii y = getfa(fa[x]);
- ans[x] = min(y.second, ans[x]);
- fa[x] = y.first;
- return make_pair(fa[x], ans[x]);
- }
- void Union(int x, int y, int c) {
- x = getfa(x).first,
- y = getfa(y).first;
- if (x == y) return;
- if (x == 1) {
- fa[y] = 1;
- ans[y] = c;
- } else if (y == 1) {
- fa[x] = 1;
- ans[x] = c;
- } else fa[x] = y;
- return;
- }
- int main() {
- n = read(),
- m = read();
- up(i, 1, n) fa[i] = i;
- up(i, 1, n) c[i][0] = ch[i][0] = read(),
- c[i][1] = ch[i][1] = read();
- up(i, 1, m) {
- x = read(),
- y = read() - 1;
- if (ch[x][y] != -1) t[++M][0] = x,
- t[M][1] = y,
- r[M] = i,
- ch[x][y] = -1;
- }
- up(i, 1, n) ans[i] = m;
- up(i, 1, n) {
- if (ch[i][0] != -1) Union(i, ch[i][0], m);
- if (ch[i][1] != -1) Union(i, ch[i][1], m);
- }
- for (int i = M; i >= 1; i--) {
- x = t[i][0],
- y = t[i][1];
- y = getfa(c[x][y]).first,
- x = getfa(x).first;
- Union(x, y, r[i] - 1);
- }
- up(i, 1, n) getfa(i);
- up(i, 1, n) printf("%d%c", ans[i] == m ? -1 : ans[i], '\n');
- return 0;
- }
来源: http://www.bubuko.com/infodetail-1869690.html