NOI 2009 植物大戰殭屍

問題簡述

有一些植物,每個植物攜帶有一定的資源(可正可負),且有一個攻擊範圍,可以保護攻擊位置上的另一個植物。有一羣殭屍從右向左進攻植物,殭屍不能走到植物的攻擊範圍內。任務是求一個進攻方案,使得殭屍獲得的資源儘可能多。

問題建模

首先我們我建立圖論模型,把每個植物當做一個頂點,植物攜帶的資源數目爲頂點的權值。如果一個植物b在另一個植物a的攻擊範圍內,連接一條有向邊<a,b>,表示a可以保護b。由於殭屍從右向左進攻,可以認爲每個植物都被它右邊相鄰的植物保護,對於每個植物a(除最左邊一列),向其左邊的相鄰植物b,連接一條有向邊<a,b>。

題目中給出的樣例建圖後如下所示

image

觀察上圖發現,{5,6}互相依賴,不可能被攻擊到。我們可以用拓撲排序去除圖中的環依賴結構,以簡化圖。

image

解法1 搜索

算法描述
建模後,直接觀察發現可以搜索。每次尋找一個入度爲0的頂點,嘗試攻擊它,更新它指向的點的入度繼續搜索。搜索中記錄選取的頂點的權值之和,保留最大值。

image

複雜度分析
搜索的時間複雜度爲O(MN)。在實際測試中得到40分。

參考程序

/*
* Problem: NOI2009 pvz
* Author: Guo Jiabao
* Time: 2009.7.29 12:01
* State: Solved
* Memo: 暴力搜索
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

const int MAXN=603,MAXM=MAXN*MAXN*4,INF=~0U>>1;

struct edge
{
    edge *next;
    int t;
}*V[MAXN],ES[MAXM];

FILE *fi,*fo;

int R,C,EC,Ans,Maxflow,Stop,S,T,N;
int score[MAXN],ind[MAXN];
bool vis[MAXN];

inline void addedge(int a,int b)
{
    ES[++EC].next = V[a]; V[a] = ES+EC; V[a]->t = b;
}

inline int point2id(int x,int y)
{
    return x * C + y + 1;
}

void init()
{
    int i,j,k,l,q,x,y,s,c;
    fi = fopen("pvz.in","r");
    fo = fopen("pvz.out","w");
    fscanf(fi,"%d%d",&R,&C);
    for (i=0;i<R;i++)
    {
        for (j=0;j<C;j++)
        {
            k = point2id(i,j);
            if (j+1<C)
            {
                q = point2id(i,j+1);
                addedge(q,k);
                ind[k]++;
            }
            fscanf(fi,"%d%d",&s,&c);
            score[k] = s;
            for (l=1;l<=c;l++)
            {
                fscanf(fi,"%d%d",&x,&y);
                q = point2id(x,y);
                addedge(k,q);
                ind[q]++;
            }
        }
    }
    N=R*C;
}

void dfs(int s)
{
    if (s > Ans)
        Ans = s;
    int i;
    edge *e;
    for (i=1;i<=N;i++)
        if (ind[i] == 0 && !vis[i])
        {
            vis[i]=true;
            for (e=V[i];e;e=e->next)
                ind[ e->t ]--;
            dfs(s+score[i]);
            vis[i]=false;
            for (e=V[i];e;e=e->next)
                ind[ e->t ]++;
        }
}

void solve()
{
    Ans = 0;
    dfs(0);
    fprintf(fo,"%d\n",Ans);
    fclose(fi);
    fclose(fo);
}

int main()
{
    init();
    solve();
    return 0;
}

解法2 最大封閉子圖

算法描述
將圖轉置後發現,一個合法的攻擊方案是一個封閉子圖(Closure of a Graph),我們的目標就是最大化攻擊方案的點權值和,就是要求一個最大封閉子圖(Maximum Weight Closure of a Graph),只需轉化爲網絡流模型,即可解決。

算法分析
樣例的圖轉置後如下,其最大封閉子圖爲{1,2,4}。

image

最大封閉子圖的玩網絡流建模方法爲:

  1. 建立附加源S和附加匯T。

  2. 圖中原有的邊容量設爲∞。

  3. 從S向每個權值爲正的點連接一條容量爲該點權值的有向邊。

  4. 從每個權值不爲正的點向T連接一條容量爲該點權值絕對值的有向邊。

在網絡上求S到T的網絡最大流Maxflow,最大封閉子圖的權值就是(所有正權點權值之和 – Maxflow)。

樣例建模後如下圖所示,求得Maxflow = 5,所以最大封閉子圖的權值爲(10 + 20 – 5) = 25。

image

求最大封閉子圖的網絡流建模方法的嚴格證明見胡伯濤《最小割模型在信息學競賽中的應用》。

複雜度分析
該圖點數爲O(NM),邊數可達O(N2M2)。拓撲排序和建圖的時間爲O(N2M2),用Dinic算法求網絡最大流的時間爲O(|V|2|E|),所以總時間複雜度爲O(N4M4)。在實際測試中通過了所以測試點,得到100分。

參考程序

/*
* Problem: NOI2009 pvz
* Author: Guo Jiabao
* Time: 2009.7.29 11:52
* State: Solved
* Memo: 最大封閉子圖 網絡最大流
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

const int MAXN=603,MAXM=MAXN*MAXN*4,INF=~0U>>1;

struct edge
{
    edge *next,*op;
    int t,c;
}*V[MAXN],*V0[MAXN],*P[MAXN],ES[MAXM],*Stae[MAXN];

FILE *fi,*fo;

int R,C,EC,Ans,Maxflow,Stop,S,T,N;
int score[MAXN],ind[MAXN],Lv[MAXN],Stap[MAXN],Q[MAXN];
bool ts[MAXN];

inline void addedge(edge **V,int a,int b,int c)
{
    ES[++EC].next = V[a]; V[a] = ES+EC; V[a]->t = b; V[a]->c=c;
    ES[++EC].next = V[b]; V[b] = ES+EC; V[b]->t = a; V[b]->c=0;
    V[a]->op = V[b]; V[b]->op = V[a];
}

inline int point2id(int x,int y)
{
    return x * C + y + 1;
}

void init()
{
    int i,j,k,l,q,x,y,s,c;
    fi = fopen("pvz.in","r");
    fo = fopen("pvz.out","w");
    fscanf(fi,"%d%d",&R,&C);
    for (i=0;i<R;i++)
    {
        for (j=0;j<C;j++)
        {
            k = point2id(i,j);
            if (j+1<C)
            {
                q = point2id(i,j+1);
                addedge(V0,q,k,1);
                ind[k]++;
            }
            fscanf(fi,"%d%d",&s,&c);
            score[k] = s;
            for (l=1;l<=c;l++)
            {
                fscanf(fi,"%d%d",&x,&y);
                q = point2id(x,y);
                addedge(V0,k,q,1);
                ind[q]++;
            }
        }
    }
    N=R*C;
}

void topsort()
{
    int i,j;
    Stop = 0;
    for (i=1;i<=N;i++)
        if (ind[i]==0)
            Stap[++Stop] = i;
    while (Stop)
    {
        i = Stap[Stop--];
        ts[i] = true;
        for (edge *e=V0[i];e;e=e->next)
        {
            j=e->t;
            if (e->c)
            {
                ind[j]--;
                if (ind[j] == 0)
                    Stap[++Stop] = j;
            }
        }
    }
}

void makegraph()
{
    int i,j;
    S=0;
    T=N+1;
    for (i=1;i<=N;i++)
        if (ts[i])
        {
            if (score[i] > 0)
            {
                addedge(V,S,i,score[i]);
                Ans += score[i];
            }
            else
                addedge(V,i,T,-score[i]);
            for (edge *e=V0[i];e;e=e->next)
            {
                j=e->t;
                if (ts[j] && e->c)
                {
                    addedge(V,j,i,INF);
                }
            }
        }
}

bool Dinic_label()
{
    int i,j,head,tail;
    memset(Lv,0,sizeof(Lv));
    Q[head=tail=0] = S;
    Lv[S] = 1;
    while (head<=tail)
    {
        i = Q[head++];
        for (edge *e=V[i];e;e=e->next)
        {
            j = e->t;
            if (Lv[j] == 0 && e->c)
            {
                Lv[j] = Lv[i]+1;
                if (j==T)
                    return true;
                Q[++tail] = j;
            }
        }
    }
    return false;
}

void Dinic_aug()
{
    int i,j,delta;
    for (i=S;i<=T;i++)
        P[i] = V[i];
    Stap[Stop=1]=S;
    while (Stop)
    {
        i = Stap[Stop];
        if (i!=T)
        {
            for (;P[i];P[i]=P[i]->next)
                if (P[i]->c && Lv[ j = P[i]->t ] == Lv[i] + 1)
                    break;
            if (P[i])
            {
                Stap[++Stop] = j;
                Stae[Stop] = P[i];
            }
            else
                Stop--,Lv[i] = 0;
        }
        else
        {
            delta = INF;
            for (i=Stop;i>=2;i--)
                if (Stae[i]->c < delta)
                    delta = Stae[i]->c;
            for (i=Stop;i>=2;i--)
            {
                Stae[i]->c -= delta;
                Stae[i]->op->c += delta;
                if (Stae[i]->c == 0)
                    Stop = i-1;
            }
            Maxflow += delta;
        }
    }
}

void Dinic()
{
    while (Dinic_label())
        Dinic_aug();
}

void solve()
{
    topsort();
    makegraph();
    Dinic();
    Ans -= Maxflow;
    fprintf(fo,"%d\n",Ans);
    fclose(fi);
    fclose(fo);
}

int main()
{
    init();
    solve();
    return 0;
}

相關日誌