HDU 4536 XCOM Enemy Unknown(DFS+回溯构造)

HDU 4536 XCOM Enemy Unknown(DFS+回溯构造)

http://acm.hdu.edu.cn/showproblem.php?pid=4536

Problem Description

XCOM-Enemy Unknown是一款很好玩很经典的策略游戏.

在游戏中,由于未知的敌人--外星人入侵,你团结了世界各大国家进行抵抗.

随着游戏进展,会有很多的外星人进攻事件.每次进攻外星人会选择3个国家攻击,作为联盟的指挥者,你要安排有限的联盟军去支援其中一个国家,抵抗进攻这个国家的外星人.

战斗胜利之后这个被支援的国家恐慌值就会-2点(恐慌值最少减为1),而其他两个未被支援的国家恐慌值就会+2点,同时和这两个国家在相同大洲的其他国家恐慌值也会+1点.

当一个国家的恐慌值超过5点,这个国家就会对联盟失去信心从而退出联盟.

现在给你外星人将会进攻的地点,问你最多能在不失去任何一个国家信任的情况下抵挡多少次外星人的进攻.

Input

第一行有一个整数T代表接下来有T组数据

每组数据第一行是三个整数,n,m,k分别代表联盟国家的个数，大洲的个数，外星人的进攻次数.

第二行是n个数字代表各个国家所属的大洲(大洲序号从0到m-1)

第三行是n个数字代表各个国家初始的恐慌值

接下去k行代表外星人进攻

每行有三个数字,表示该次外星人进攻的国家(国家序号从0到n-1)

[Technical Specification]

0<T<=100

8<n<=16

2<m<=5

0<k<=100

0<初始恐慌值<=5

每个州至少有三个国家

每次外星人进攻一定发生在不同州的三个国家

Output

首先输出case数(见sample),接着输出在不失去任何一个国家的情况下能抵挡外星人进攻最多的次数.

Sample Input

1

9 3 2

0 0 0 1 1 1 2 2 2

3 3 3 3 3 3 3 3 3

0 3 6

0 3 6

Sample Output

Case #1: 1

Hint

第一次如果选择了0,那么3和6的恐慌值就会增加到5,第二次不管怎么选择,3和6总会有一个超过5.

分析：

首先注意到国家总数很少，所以我们可以对于每次攻击，依次枚举3个国家中的任意一个作为可能被攻击的国家，然后继续DFS，看看最多能走多深。

注意：每个州至少有三个国家且每次外星人进攻一定发生在不同州的三个国家。

首先我们用：

struct country

{

intbe; //州

intval; //恐慌值

}C[maxn];

来表示所有国家的状态，我们每次DFS往前走一步，以C[MAXN]的值就变成新状态的值,然后我们判断当前状态是否合法,如果合法就可以继续往前走.如果不合法,那么就用当前DFS深度更新ans即可.然后在试探当前选择之后还要还原C[maxn]的状态,以便在当前深度我们可以尝试另外两种选择.(即回溯)

总结:其实DFS回溯构造就是一直维持一个仅有的当前状态,然后不断的往前DFS尝试,找到合法的解.而BFS的过程是要产生很多状态的.

AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=16+5;
const int maxa=100+5;
int T,n,m,k;
int ans;//解
struct country
{
    int be;     //州
    int val;    //恐慌值
}C[maxn];
struct ack
{
    int c1,c2,c3;
}A[maxa];
bool ok()
{
    for(int i=0;i<n;i++)if(C[i].val>5) return false;
    return true;
}
void dfs(int p)
{
    ans=max(ans,p);
    if(p>=k) return ;//已经处理完所有攻击

    int a1=A[p].c1;
    int a2=A[p].c2;
    int a3=A[p].c3;
    int old_val;
    //尝试援救第一个国家
    old_val=C[a1].val;
    C[a1].val= C[a1].val-2>=1? C[a1].val-2:1;
    C[a2].val+=2;
    C[a3].val+=2;
    for(int i=0;i<n;i++)
    {
        if(C[i].be==C[a2].be && i!=a2) C[i].val++;
        if(C[i].be==C[a3].be && i!=a3) C[i].val++;
    }
    if(ok())//当前状态合法
        dfs(p+1);
    C[a1].val=old_val;//回溯
    C[a2].val-=2;
    C[a3].val-=2;
    for(int i=0;i<n;i++)
    {
        if(C[i].be==C[a2].be && i!=a2) C[i].val--;
        if(C[i].be==C[a3].be && i!=a3) C[i].val--;
    }
    //尝试援救第二个国家
    old_val=C[a2].val;
    C[a1].val+=2;
    C[a2].val= C[a2].val-2>=1? C[a2].val-2:1;
    C[a3].val+=2;
    for(int i=0;i<n;i++)
    {
        if(C[i].be==C[a1].be && i!=a1) C[i].val++;
        if(C[i].be==C[a3].be && i!=a3) C[i].val++;
    }
    if(ok())//当前状态合法
        dfs(p+1);
    C[a1].val-=2;//回溯
    C[a2].val=old_val;
    C[a3].val-=2;
    for(int i=0;i<n;i++)
    {
        if(C[i].be==C[a1].be && i!=a1) C[i].val--;
        if(C[i].be==C[a3].be && i!=a3) C[i].val--;
    }
    //尝试援救第3个国家
    old_val=C[a3].val;
    C[a1].val+=2;
    C[a2].val+=2;
    C[a3].val =C[a3].val-2>=1? C[a3].val-2:1;
    for(int i=0;i<n;i++)
    {
        if(C[i].be==C[a1].be && i!=a1) C[i].val++;
        if(C[i].be==C[a2].be && i!=a2) C[i].val++;
    }
    if(ok())//当前状态合法
        dfs(p+1);
    C[a1].val-=2;//回溯
    C[a2].val-=2;
    C[a3].val=old_val;
    for(int i=0;i<n;i++)
    {
        if(C[i].be==C[a1].be && i!=a1) C[i].val--;
        if(C[i].be==C[a2].be && i!=a2) C[i].val--;
    }
}
int main()
{
    scanf("%d",&T);
    for(int kase=1;kase<=T;kase++)
    {
        scanf("%d%d%d",&n,&m,&k);
        for(int i=0;i<n;i++)//国家从0开始编号
            scanf("%d",&C[i].be);
        for(int i=0;i<n;i++)//国家从0开始编号
            scanf("%d",&C[i].val);
        for(int i=0;i<k;i++)
            scanf("%d%d%d",&A[i].c1,&A[i].c2,&A[i].c3);
        ans=0;//递归深度
        dfs(0);//0表当前还未处理一个攻击
        printf("Case #%d: %d\n",kase,ans);
    }
    return 0;
}