首页 > ACM题库 > HDU-杭电 > HDU 4297-One and One Story-并查集-[解题报告]HOJ
2015
05-23

HDU 4297-One and One Story-并查集-[解题报告]HOJ

One and One Story

问题描述 :

  Have you ever played the romantic Flash game, "One and One Story"?1 In this story of a boy and a girl and their romance you are to direct them to meet together as they face their euphoria and trials of their relationship.
  You, as a member of the FFF Inquisition, 2 are fed up with such game since you believe that to make things fair, you should not keep providing guidance information while risking remaining forever alone 3 . So you decided to write a program working out guidance for these sweet small lovers on behalf of you. ( Another reason is, you have to help K couples, which would make you somewhat overwhelmed. )
  Fortunately, you are to handle not the Flash game above, but a simplified version: In the game, a maze consists of some rooms connected with one-way hallways. For each room, there is exactly one outgoing hallway here, and it would lead directly to some room (not necessarily a different one). The boy and girl are trapped in (not necessarily different) rooms. In each round of the games, both of them could choose to stay in the current room or walk to the room to which the unique outgoing hallway leads. Note that boy and girl could act independently of each other. Your goal is to come to the reunion between them.
  Your program should determine a pair of numbers (A,B) for each couple of boy and girl, where A represents number of hallway the boy walked through, B the girl, that could lead reunion between them. First, your program should minimize max(A,B). If there are several solutions, you should then guarantee that min(A,B) is minimized subject to above. If, satisfying above conditions, there are still multiple solutions, girl should walk less, that is you should then keep A >= B subject to conditions above.
  In case they could not reunion, just let A = B = -1.
———————————————————————————
1It’s available here: http://armorgames.com/play/12409/one-and-one-story
2See http://bakatotest.wikia.com/wiki/FFF_Inquisition
3http://foreveralonecomic.com/

输入:

  There’re several test cases.
  In each test case, in the first line there are two positive integers N and K (1 <= N <= 500000; 1 <= K <= 500000) denoting the number of rooms and number of couples. Rooms a numbered from 1 to N.
  The second line contains n positive integers: the ith integer denotes the number of room to which the hallway going out of room i leads.
The following K lines are queries of several couples. Each query consists of two positive integers in a single line denoting the numbers of rooms where the lovers currently are: first the boy, then the girl.
  Please process until EOF (End Of File).

输出:

  There’re several test cases.
  In each test case, in the first line there are two positive integers N and K (1 <= N <= 500000; 1 <= K <= 500000) denoting the number of rooms and number of couples. Rooms a numbered from 1 to N.
  The second line contains n positive integers: the ith integer denotes the number of room to which the hallway going out of room i leads.
The following K lines are queries of several couples. Each query consists of two positive integers in a single line denoting the numbers of rooms where the lovers currently are: first the boy, then the girl.
  Please process until EOF (End Of File).

样例输入:

12 5
4 3 5 5 1 1 12 12 9 9 7 1
7 2
8 11
1 2
9 10
10 5
12 5
4 3 5 5 1 1 12 12 9 9 7 1
7 2
8 11
1 2
9 10
10 5

样例输出:

2 3
1 2
2 2
0 1
-1 -1
2 3
1 2
2 2
0 1
-1 -1

题意:给定一个有向图,每个节点只有一条出边,现在两个人在两个节点沿着有向边走,按照题意输出相遇时两个人走的路径。
题解:这个有向图很特别,由于每个节点只有一条出边,所以如果形成一个环的话就只能有指向这个环的边,同时一个子图内最多存在一个环,tarjan搞掉环,
         建反图虚拟根节点转换成一棵树,根节点如果是环的环用带关系的并查集维护,然后lca->rmq,在线得到答案。
         每次lca->rmq总是一串代码…

Sure原创,转载请注明出处。

#pragma comment (linker , "/STACK:1024000000,1024000000")
#include <iostream>
#include <cstdio>
#include <memory.h>
#include <cmath>
#define MIN(a , b) ((a) < (b) ? (a) : (b))
#define MAX(a , b) ((a) > (b) ? (a) : (b))
using namespace std;
const int maxn = 500002;
struct node
{
    int v;
    int next;
}edge[maxn << 1];
int up[maxn],down[maxn],head[maxn],father[maxn],dis[maxn];
int dfn[maxn],low[maxn],s[maxn],belong[maxn],cnt[maxn],indegree[maxn];
int E[maxn << 1],D[maxn << 1],bj[maxn],dep[maxn],dp[maxn << 1][20];
bool vis[maxn],instack[maxn];
int m,n,idx,tmpdfn,tot,top,bound;

void init()
{
    memset(head,-1,sizeof(head));
    memset(cnt,0,sizeof(cnt));
    memset(vis,false,sizeof(vis));
    memset(instack,false,sizeof(instack));
    idx = tmpdfn = 0;
    tot = 1;
    return;
}

inline void in(int &a)
{
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9');
    a = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9')
    {
        a = a * 10 + ch - '0';
    }
    return;
}

void swap(int &a,int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
    return;
}

int find(int u)
{
    if(u == father[u]) return father[u];
    int tmp = father[u];
    father[u] = find(tmp);
    dis[u] += dis[tmp];
    return father[u];
}

void addedge(int u,int v)
{
    edge[idx].v = v;
    edge[idx].next = head[u];
    head[u] = idx++;
    return;
}

void read()
{
    for(int i=1;i<=n;i++)
    {
        father[i] = i;
        in(down[i]);
        addedge(i , down[i]);
    }
    return;
}

void tarjan(int st)
{
    dfn[st] = low[st] = tmpdfn++;
    vis[st] = instack[st] = true;
    s[top++] = st;
    for(int i=head[st];i != -1;i=edge[i].next)
    {
        if(vis[edge[i].v] == false)
        {
            tarjan(edge[i].v);
            low[st] = MIN(low[st] , low[edge[i].v]);
        }
        else if(instack[edge[i].v])
        {
            low[st] = MIN(low[st] , dfn[edge[i].v]);
        }
    }
    if(dfn[st] == low[st])
    {
        int u;
        do
        {
            u = s[--top];
            instack[u] = false;
            belong[u] = tot;
            cnt[tot]++;
        }while(u != st);
        tot++;
    }
    return;
}

void reset()
{
    memset(head,-1,sizeof(head));
    memset(up,-1,sizeof(up));
    memset(dis,0,sizeof(dis));
    memset(indegree,0,sizeof(indegree));
    memset(dep,0,sizeof(dep));
    idx = top = 0;
    return;
}

void make()
{
    for(int i=1;i<=n;i++)
    {
        if(vis[i] == false)
        {
            top = 0;
            tarjan(i);
        }
    }
    reset();
    for(int i=1;i<=n;i++)
    {
        int u = belong[down[i]];
        int v = belong[i];
        if(u != v)
        {
            addedge(u,v);
            indegree[v]++;
            if(cnt[u] > 1)
            {
                up[v] = down[i];
            }
        }
        else
        {
            int x = find(down[i]);
            int y = find(i);
            if(x != y)
            {
                father[y] = x;
                dis[y] = dis[down[i]] + 1;
            }
        }
    }
    for(int i=1;i<tot;i++)
    {
        if(indegree[i] == 0)
        {
            addedge(0,i);
        }
    }
    return;
}

void dfs(int st,int h)
{
    dep[st] = h;
    E[++top] = st;
    D[top] = h;
    bj[st] = top;
    for(int i=head[st];i != -1;i=edge[i].next)
    {
        if(up[edge[i].v] == -1)
        {
            up[edge[i].v] = up[st];
        }
        dfs(edge[i].v , h+1);
        E[++top] = st;
        D[top] = h;
    }
    return;
}

void init_rmq()
{
    for(int i=1;i<=top;i++)
    {
        dp[i][0] = i;
    }
    for(int j=1;j<=bound;j++)
    {
        for(int i=1;i + (1 << j) - 1 <= top;i++)
        {
            if(D[dp[i][j-1]] < D[dp[i + (1 << (j-1))][j-1]])
            {
                dp[i][j] = dp[i][j-1];
            }
            else
            {
                dp[i][j] = dp[i + (1 << (j-1))][j-1];
            }
        }
    }
    return;
}

int askrmq(int l,int r)
{
    if(l > r) swap(l , r);
    int d = log((double)(r - l + 1)) / log(2.0);
    int wei = -1;
    if(D[dp[l][d]] < D[dp[r - (1 << d) + 1][d]])
    {
        wei = dp[l][d];
    }
    else
    {
        wei = dp[r - (1 << d) + 1][d];
    }
    return E[wei];
}

void solve()
{
    dfs(0,0);
    bound = log((double)(top + 1)) / log(2.0);
    init_rmq();
    int u,v;
    while(m--)
    {
        in(u),in(v);
        if(u == v)
        {
            puts("0 0");
            continue;
        }
        int x = belong[u];
        int y = belong[v];
        int lca = askrmq(bj[x] , bj[y]);
        if(lca == 0)
        {
            puts("-1 -1");
            continue;
        }
        else if(cnt[lca] == 1)
        {
            printf("%d %d\n",dep[x] - dep[lca],dep[y] - dep[lca]);
            continue;
        }
        int dx,dy,dxy,dyx;
        if(x == y)
        {
            dx = dy = 0;
            find(u),find(v);
            if(dis[u] < dis[v])
            {
                dxy = cnt[x] + dis[u] - dis[v];
                dyx = dis[v] - dis[u];
            }
            else
            {
                dxy = dis[u] - dis[v];
                dyx = cnt[x] - dxy;
            }
        }
        else
        {
            dx = dep[x] - dep[lca];
            dy = dep[y] - dep[lca];
            if(cnt[lca] == 1)
            {
                dxy = dyx = 0;
            }
            else
            {
                u = (up[x] == -1) ? u : up[x];
                v = (up[y] == -1) ? v : up[y];
                find(u),find(v);
                if(dis[u] < dis[v])
                {
                    dxy = cnt[lca] + dis[u] - dis[v];
                    dyx = dis[v] - dis[u];
                }
                else
                {
                    dxy = dis[u] - dis[v];
                    dyx = cnt[lca] - dxy;
                }
            }
        }
        if(MAX(dx+dxy , dy) < MAX(dx , dy+dyx))
        {
            printf("%d %d\n",dx+dxy , dy);
        }
        else if(MAX(dx+dxy , dy) > MAX(dx , dy+dyx))
        {
            printf("%d %d\n",dx , dy+dyx);
        }
        else
        {
            if(MIN(dx+dxy , dy) < MIN(dx , dy+dyx))
            {
                printf("%d %d\n",dx+dxy , dy);
            }
            else if(MIN(dx+dxy , dy) > MIN(dx , dy+dyx))
            {
                printf("%d %d\n",dx , dy+dyx);
            }
            else
            {
                printf("%d %d\n",MAX(dx+dxy , dy),MIN(dx , dy+dyx));
            }
        }
    }
    return;
}

int main()
{
    while(~scanf("%d %d",&n,&m))
    {
        init();
        read();
        make();
        solve();
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/flying_stones_sure/article/details/7996170