【海岛帝国系列赛】No.6 海岛帝国：战争前线

50234237海岛帝国：战争前线

【试题描述】

总指挥官WHT出神入化的计谋虽然大有用武之地，但是聪明的恐怖分子们采取了城市核武器防御系统，可以有效地抵制WHT的炸弹。YSF对此头痛不已，因此召开了一次国家性大会。在会上，WHT、LJX、LTJ等人均提出了战略方针。可全部被拒绝。WHT对核武器防御系统是一筹莫展。如果再迟几天，敌人的核武器就会全部生产完毕并开始狂轰滥炸。就在这危难之时，匆匆忙忙从美国的卡内基梅隆大学作为博士生赶回的YSM掌握了此消息。于是，他提出：如果使用核武器炸断敌军的路，或许就能解围。没有主见的WHT也采取了他的办法，照抄照办。WHT掌握着很多很多枚“蝴蝶”。他要启动计划B。然而由于形势日益紧张， “药师傅”帝国资源极其稀缺，WHT想用很快的方法来求出最少需要炸断几条路，才能使整个敌国的城市不连通，正常人不可能很快做到这一点，所以，他请你来编个程序告诉他。

【输入要求】

* 第一行两个正整数N,M，表示有N个城市，有M条路
* 接下来M行：每行两个数A,B表示城市A和B之间有一条路相连

【输出要求】

在做到使整个敌国的城市不连通炸的路最少的情况下，输出要炸的路，形如a-b，回车分隔。

【输入实例】

6 6
1 4
1 3
4 2
3 2
2 5
5 6

【输出实例】

5-6
2-5

【其他说明】

M均小于40
N均小于10

【试题分析】

其实想一想，只需要更改求割点的一个符号而已：low[v]>=num[u] => low[v]>num[u]，为什么呢？low[v]>=num[u]代表的是点v是不可能在经过父亲节点u而回到祖先的，所以顶点u是割点，如果low[v]和num[u]相等，则表示还可以回到父亲节点u而回到父亲，而low[v]>num[u]则表示连父亲都回不到了。如果顶点V不能回到祖先，也没有另一条路能回到父亲，那么u-v这条边就是割边。

【代码】

 #include<iostream>

 using namespace std;

 int n,m,e[][],root;

 int num[],low[],index;

 void dfs(int cur,int father)

 {

     int i;

     index++;

     num[cur]=index;

     low[cur]=index;

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

     {

         if(e[cur][i]==)

         {

             if(num[i]==)

             {

                 dfs(i,cur);

                 low[cur]=min(low[cur],low[i]);

                 if(low[i]>num[cur]) printf("%d-%d\n",cur,i);

             }

             else if(i!=father) low[cur]=min(low[cur],num[i]);

         }

     }

     return;

 }

 int main()

 {

     int x,y;

     cin>>n>>m;

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

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

             e[i][j]=;

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

     {

         cin>>x>>y;

         e[x][y]=;

         e[y][x]=;

     }

     root=;

     dfs(,root);

 }

巴特西

【海岛帝国系列赛】No.6 海岛帝国：战争前线

最新文章

热门文章