2014 Super Training #10 C Shadow --SPFA/随便搞/DFS

原题： FZU 2169 http://acm.fzu.edu.cn/problem.php?pid=2169

这题貌似有两种解法，DFS和SPFA，但是DFS怎么都RE，SPFA也要用邻接表表示边，用向量表示的话会TLE，而且用SPFA有一个异或，就是题目说要沿最短路走到都城，但是SPFA是走最短路去消灭叛军，然后再走回都城，我不知道怎么回事，不知道能不能有大神解释。因为这样的话，有多少叛军就能消灭多少叛军了，那就不要用什么算法了，直接一个统计。于是试了一下，居然A了，瞬间变成大水题，我无法再评价这个题目了，就当消遣了。

SPFA法：依次从每个军队城市出发做一次SPFA，看到有能到的（肯定能到啊）叛军就将其消灭。

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <cstdlib>

#include <queue>

#define Mod 1000000007

using namespace std;

#define N 100007

struct Edge

{

    int v,next;

}G[*N];

int head[N],tot;

int army[N],rebel[N];

int vis[N],dis[N];

int res;

int n,m;

void addedge(int u,int v)

{

    G[tot].v = v;

    G[tot].next = head[u];

    head[u] = tot++;

}

void SPFA(int s)

{

    int i;

    memset(vis,,sizeof(vis));

    queue<int> que;

    while(!que.empty())

        que.pop();

    que.push(s);

    vis[s] = ;

    dis[s] = ;

    while(!que.empty())

    {

        int tmp = que.front();

        que.pop();

        vis[tmp] = ;

        for(i=head[tmp];i!=-;i=G[i].next)

        {

            int v = G[i].v;

            if(dis[v] > dis[tmp] + )

            {

                dis[v] = dis[tmp]+;

                if(!vis[v])

                {

                    que.push(v);

                    vis[v] = ;

                }

            }

        }

    }

}

int main()

{

    int i,j,x;

    int u,v;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        memset(army,,sizeof(army));

        memset(rebel,,sizeof(rebel));

        memset(head,-,sizeof(head));

        tot = ;

        int cnt = ;

        for(i=;i<=n;i++)

        {

            scanf("%d",&rebel[i]);

            if(rebel[i])

                cnt++;

        }

        for(i=;i<=m;i++)

            scanf("%d",&army[i]);

        for(i=;i<n-;i++)

        {

            scanf("%d%d",&u,&v);

            addedge(u,v);

            addedge(v,u);

        }

        res = ;

        for(i=;i<=m;i++)

        {

            SPFA(army[i]);

            for(j=;j<=n;j++)

            {

                if(dis[j] != Mod)

                {

                    if(rebel[j])

                    {

                        res += rebel[j];

                        rebel[j] = ;

                        cnt--;

                    }

                }

            }

            if(cnt == )  //已经消灭完

                break;

        }

        printf("%d\n",res);

    }

    return ;

}

DFS法（选GNU C++ 会Runtime Error，要选Visual C++）：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <cstdlib>

#include <algorithm>

#define Mod 1000000007

#define ll long long

using namespace std;

#define N 100007

struct Edge

{

    int v,next;

}G[*N];

int head[N],tot;

int army[N],rebel[N];

ll sum;

int n,m;

void addedge(int u,int v)

{

    G[tot].v = v;

    G[tot].next = head[u];

    head[u] = tot++;

}

int dfs(int u,int val,int fa)

{

    int soni = ;

    if(army[u])  //找到军队

    {

        sum += val;

        soni++;

    }

    for(int i=head[u];i!=-;i=G[i].next)

    {

        int v = G[i].v;

        if(v == fa)

            continue;

        soni += dfs(v,val+rebel[u],u);

    }

    if(soni > )

        sum -= (soni-)*rebel[u];

    return soni;

}

int main()

{

    int i,j,x;

    int u,v;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        memset(army,,sizeof(army));

        memset(rebel,,sizeof(rebel));

        memset(head,-,sizeof(head));

        tot = ;

        for(i=;i<=n;i++)

            scanf("%d",&rebel[i]);

        for(i=;i<=m;i++)

        {

            scanf("%d",&x);

            army[x] = ;

        }

        for(i=;i<n-;i++)

        {

            scanf("%d%d",&u,&v);

            addedge(u,v);

            addedge(v,u);

        }

        sum = ;

        dfs(,,-);

        printf("%lld\n",sum);

    }

    return ;

}

直接统计：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

using namespace std;

#define N 100007

int army[N],rebel[N];

int res;

int n,m;

int main()

{

    int i,j,x;

    int u,v;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        memset(rebel,,sizeof(rebel));

        int cnt = ;

        res = ;

        for(i=;i<=n;i++)

        {

            scanf("%d",&rebel[i]);

            if(rebel[i])

                res += rebel[i];

        }

        for(i=;i<=m;i++)

            scanf("%d",&army[i]);

        for(i=;i<n-;i++)

            scanf("%d%d",&u,&v);

        if(m == )

        {

            puts("");

            continue;

        }

        printf("%d\n",res);

    }

    return ;

}

巴特西

2014 Super Training #10 C Shadow --SPFA/随便搞/DFS

最新文章

热门文章