首页 > 搜索 > BFS搜索 > HDU 3313-Key Vertex-BFS-[解题报告]HOJ
2014
03-16

HDU 3313-Key Vertex-BFS-[解题报告]HOJ

Key Vertex

问题描述 :

You need walking from vertex S to vertex T in a graph. If you remove one vertex which stops you from walking from S to T, that vertex we call as key vertex. Now you are given a directed graph, S and T, and you should tell us how many key vertexes are there in the graph.
Please notice that S and T are key vertexes and if S cannot walking to T by the directed edge in the initial graph then all vertexes becomes to key vertexes.

输入:

The input consists of multiply test cases. The first line of each test case contains two integers, n(0 <= n <= 100000), m(0 <= m <= 300000), which are the number of vertexes and the number of edge. Each of the next m lines consists of two integers, u, v(0 <= u, v < n; u != v), indicating there exists an edge from vertex u to vertex v. There might be multiple edges but no loops. The last line of each test case contains two integers, S, T(0 <= S, T < n, S != T).

输出:

The input consists of multiply test cases. The first line of each test case contains two integers, n(0 <= n <= 100000), m(0 <= m <= 300000), which are the number of vertexes and the number of edge. Each of the next m lines consists of two integers, u, v(0 <= u, v < n; u != v), indicating there exists an edge from vertex u to vertex v. There might be multiple edges but no loops. The last line of each test case contains two integers, S, T(0 <= S, T < n, S != T).

样例输入:

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

样例输出:

4

 

题意: 给一个图,给起点终点,S,T; 如果删除一个点,使得无法从S到T,则这个点事可删点,问有多少个可删点 ;

 据说可以用最小割写,不过还是来个朴素的A题解法 ;

首先,我们先找到一条从S到T的路径,当然可以直接找最短路,至此我们可以知道,除了这条路上的其他点,都不是可删点了,因为就算你删除了那些点,也照样可以通过这条路到达T; 然后,可删点就是这条路上的某些点了;我们可以在这条路上从起点S可是搜;我们bfs的控制条件是;如果当前搜到的点不在这条路上,就进队,若在就补进队;

同事更新;  那么我们可以想到;当整个bfs结束后,必然是因为最后搜到一个点,这个点事在那条路上的,因为搜到的点在这条路上,不进队,所以导致队列空了,程序结束;

所以当bfs结束后,最后搜到的点就是可删点;因为搜到这个点就搜不下去了,也就是没路了,说明这个点是决定能否继续往后面通过的点,那么删除这个点,珍格格图断了,当然就无法到达T了,

 

#include<stdio.h>
#include<vector>
#include<iostream>
#include<queue>
using namespace std;
#define maxn 100001
#define maxm 300001
int Start,End,pre[maxn],vis[maxn],low[maxn],Top,head[maxn];;

struct edge 
{
    int y, next;
} e[maxm];
void insert(int x, int y)
{
     e[Top].y=y;
     e[Top].next = head[x];
     head[x] = Top++;
}

void ini(int n)
{
    Top=0;
    for(int i=0;i<=n;i++)
    {
        vis[i]=low[i]=0;
        head[i]=-1;
    }
}
int Bfs1(int u)            //找最短路 
{
    int w,p;
    pre[u]=-1;
    queue<int>q;
    q.push(u);
    vis[u]=1;
    while(!q.empty())
    {
        u=q.front();
        q.pop();
         for (p = head[u]; p != -1; p = e[p].next)
         {
             w= e[p].y;
            if(vis[w]==0)
            {
                q.push(w);
                vis[w]=1;
                pre[w]=u;
                if(w==End)return 1;
            }
        }
    }
    return 0;
}
int Bfs2(int u)             //搜可删点 
{
    int w,res=u,p;
    queue<int>q;
    q.push(u);
    while(!q.empty())
    {
        u=q.front();
        q.pop();
         for (p = head[u]; p != -1; p = e[p].next)
         {
             w= e[p].y;
            if(vis[w]==0)
            {
                vis[w]=1;
                if(low[w]==0)q.push(w);     //如果点不在最短路上,进队 
                else if(low[res]>low[w])res=w;  //在最短路上,则更新res, 
            }

        }
    }
    return res;      //最终结束得到的可删点 
}
int main()
{
    int n,m,i,j,x,y;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        ini(n);
         for ( i = 0; i < m; ++i) {
             int a, b;
             scanf("%d%d", &a, &b);
             insert(a, b);
         }
        scanf("%d%d",&Start,&End);
        if(n==0||n==1)
        {
            printf("%d\n",n);
            continue;
        }
        if(!Bfs1(Start))       //图是不联通的,则左右点都可删 
        {
            printf("%d\n",n);
            continue;
        }
        else
        {
             i=End;
             int top=1;
             while(pre[i]!=-1)     //记录找的的最短路; 
             {
                  low[i]=top++;
                   i=pre[i];
             }
             low[Start]=top;
        }
        int res=1;   
        for(i=0;i<n;i++)vis[i]=0;
        i=Start;
        vis[Start]=1;
        while(i!=End)   //从起点开始搜,没BFS2一次,得到一个可删点 
        {
            i=Bfs2(i);
            res++;
        }
        printf("%d\n",res);
    }
    return 0;
}

 

参考:http://blog.csdn.net/u010126535/article/details/17099859


,
  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. if(j){
    int ans=a ;
    for(int x=j-1;x>=0;x–){
    if(!a ) break;
    ans=min(ans,a );
    sum+=ans;
    }
    }
    求解释,,dp的思路是什么呢?

  3. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  4. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。

  5. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

  6. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;