北师大 ------ 星际战争

                                                                         星际战争



题目描述:

   公元3500年,地球与一个叫卡拉星的外星系星球之间发生了一场大规模的战争。这场战争打得异常激烈,足足持续了一百多年。随着战事的发展,地球人渐渐落到了下风。按理说地球人的装备比卡拉星人的装备还要好一些,是什么原因导致这样的战局呢?原来,地球军队的新上任的司令官是一个很糊涂的家伙,刚愎自用,却常常做出一些错误的决策,贻误战机。这样的情况多次发生,形势对地球人来说就越来越不利了。
这时候,地球军队的参谋们已经看到了他们军队首领的实质,但他们并没有权力革除司令官的职务,所以他们必须找到一个巧妙的办法来扭转战局。于是,一个聪明的参谋提出,每次制订作战方案的时候,他们就预先准备好多套作战方案,供司令官选用。由于司令官本来就糊涂,当然更愿意从已有的方案中选择。另一方面,由于选择哪套作战方案是由司令官决定的,他也会对自己行使了最终决策权感到很满意。而对参谋们来说,他们要做的事情是制订满足以下条件的多套作战方案:不论司令官选择了哪一套方案,最终都保证成功实现正确的作战目的。
好了,新的战斗马上就要打响了!
这一次的作战任务是切断卡拉星球的一条后勤运输线。侦察部队带回的结果已经非常清楚的表明,卡拉星球有n个城市,编号为1——n,这些城市与城市之间以能够双向行驶的公路相连接。所有公路的分布情况都已掌握。卡拉星球的一个重要后勤据点位于城市s,他们最近将要运输大量的后勤物资到达位于城市t的前沿阵地。地球军决定通过摧毁某些公路,切断s城与t城之间的联系。
那个聪明的参谋要开始准备作战方案了。他首先仔细研究了卡拉星球的所有公路的信息,然后开始决定每一套作战方案的内容,即本次作战具体要摧毁哪些公路。他希望制订的多套方案看上去是完全不同的(这样才能更好的迷惑司令官),也就是任意的两套不同的方案中不会出现相同的摧毁目标。另外,为了使司令官尽量满意,他希望备选作战方案的数目尽可能多。问题这就来了,备选作战方案最多究竟能够有多少套呢?
你来帮帮我们的英雄吧,也为拯救我们地球贡献一份力量。

Input

输入包括多组测试数据,每组测试数据第一行包括四个正整数n (2 ≤ n ≤ 10000)、m (1 ≤ m ≤ 1000000)、s (1 ≤ s ≤ n) 和t (1 ≤ t ≤ n),分别表示卡拉星球的城市的个数、公路的条数、后勤据点所在城市编号和前沿阵地所在城市编号。输入保证后勤据点和前沿阵地必定不在同一城市且从后勤据点必定能通过公路到达前沿阵地。
以下m行描述了卡拉星球公路的分布状况。每行有两个整数i (1 ≤ i ≤ n) 和j (1 ≤ j ≤ n),表示在城市编号为i和j的城市之间有一条公路。
n = m = s = t = 0 表示输入结束。

Output

对于每组输入数据,请输出一行答案,即备选作战方案最多可能有多少套。

Sample Input

2 1 1 2
1 2
0 0 0 0

Sample Output

1



算法分析:

    一道我个人感觉是Spfa的算法构造题。

    就是在从起点开始到终点的路上,看经过了哪些点。而同一层次的点有属于同一种方法,所以其实这题还有点是搜索题。就是把点一层一层的搜索,每经过一层都是一种方案。想想为什么?这个是解题的关键。因为,在同一层中只有把这一层的路都给删了,才能使得图不连通。而这样子同一层的点当然就归入了同一个方案。所以从起点开始,一层一层的走,走到终点,统计最后的方案数就可以了。不过有很多细节,一不注意就Over 了,当时全场比赛就我一个人在那里傻傻的做这题,幸好最后我AC了。

   当时比赛的时候我错了30+!!!吐血啊。。。因此这么坑的题当时全程就一人孤独的过了。


#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 1e4 + 5;
struct Edge{
   int from,to,dist;
}edges;
vector<int> G[maxn];
int d[maxn];
bool inq[maxn];
queue<int> Q;
void Init()
{
    for(int i = 0;i < maxn;++i)
      G[i].clear();
    memset(d,-1,sizeof(d));
    memset(inq,false,sizeof(inq));
    while(!Q.empty())Q.pop();
}
int Spfa(int s,int t)
{
    d[s] = 0;
    Q.push(s);
    while(!Q.empty()){
        int u = Q.front();
        Q.pop();
        inq[u] = false;
        for(int i = 0;i < (int)G[u].size();++i){
           int v = G[u][i];
           if(d[v]<0){       //tong yi ge jie dian,wu xu chong fu ji suan
               d[v] = d[u]+1;
               if(v==t)goto Lable;
               if(!inq[v]){
                  inq[v] = true;
                  Q.push(v);
               }
           }
        }
    }

    Lable:
//    for(int i = 1; i <= t;++i)
//      printf("%d ---> %d\n",i,d[i]);
    if(d[t]==-1)
      d[t] = 0;
    return d[t];
}
int main()
{
    int n,m,s,t;
    while(scanf("%d%d%d%d",&n,&m,&s,&t),(n||m||s||t))
    {
        Init();
        int from,to;
        for(int i = 0;i < m;++i){
           scanf("%d%d",&from,&to);
           G[from].push_back(to);
           G[to].push_back(from);
        }
        printf("%d\n",Spfa(s,t));
    }
    return 0;
}







相关文章
相关标签/搜索