FZOJ 2188 过河I （确定状态+BFS）

Problem Description

Input

Output

Sample Input

Sample Output

Hint

第一个样例

次数 船 方向 左岸 右岸（狼 羊）

0： 0 0 3 3 0 0

1： 2 0 > 1 3 2 0

2： 1 0 < 2 3 1 0

3： 2 0 > 0 3 3 0

4： 1 0 < 1 3 2 0

5： 0 2 > 1 1 2 2

6： 1 1 < 2 2 1 1

7： 0 2 > 2 0 1 3

8： 1 0 < 3 0 0 3

9： 2 0 > 1 0 2 3

10： 1 0 < 2 0 1 3

11： 2 0 > 0 0 3 3

思路：求最少的次数，可以想到bfs，关键是确定好状态

设vis[x][y][2] 表示船到达0或1岸后，此岸上的羊数x，和狼数y

而且题目的限制条件很多，可以有很多剪枝，出解很快

//Accepted 2576 625ms GNU C++ 
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 1e5+100;

int head[N];
struct Edge
{
    int to;
    int next;
}es[N<<1];


int son[N];
int n;
int ans1,ans2;
void dfs(int rt,int pa)
{
    int cnt=0;
    bool first=1;
    for(int i=head[rt];~i;i=es[i].next)
    {
        int v=es[i].to;
        if(v==pa) continue;
        if(first)
            first=0;
        else
        {
            ans1++;
            cnt++;
        }
        dfs(v,rt);
    }
    ans2+=cnt/2+cnt%2; //剔除同一节点的分枝数
}

void ini()
{
    memset(head,-1,sizeof(head));
    memset(son,0,sizeof(son));
    ans1=ans2=0;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        ini();
        for(int v=1;v<n;v++)
        {
            int u;
            scanf("%d",&u);
            es[v].to=v;
            es[v].next=head[u];
            head[u]=v;
            es[v+n].to=u;
            es[v+n].next=head[v];
            head[v]=v+n;
            son[u]++;
            son[v]++;
        }
        for(int i=n-1;i>=0;i--)
            if(son[i]==1)
            {
                dfs(i,-1);
                ans1++;
                ans2++;
                break;
            }
        if(ans1)
            printf("%d %d\n",(ans1-1)/2+(ans1-1)%2+1,ans2);
        else
            printf("0 0\n");
    }
    return 0;
}