2014
03-16

# 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

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

#include<stdio.h>
#include<vector>
#include<iostream>
#include<queue>
using namespace std;
#define maxn 100001
#define maxm 300001

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

void ini(int n)
{
Top=0;
for(int i=0;i<=n;i++)
{
vis[i]=low[i]=0;
}
}
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;
}

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;