首页 > ACM题库 > HDU-杭电 > HDU 3896-Greatest TC[解题报告]HOJ
2015
04-13

HDU 3896-Greatest TC[解题报告]HOJ

Greatest TC

问题描述 :

TC (Tian Chao) is magical place, as you all know…
The railways and the rail-stations in TC are fragile and always meet with different kinds of problems. In order to reach the destination safely on time, you are asked to develop a system which has two types of main functions as below.
1: A B C D, reporting whether we can get from station A to station B without passing the railway that connects station C and station D.
2: A B C, reporting whether we can get from station A to station B without passing station C.
Please notice that the railways are UNDIRECTED.

输入:

For each test case, the first line will contain two integers N (2<=N<=100000) and M (1<=M<=500000), namely the number of stations and railways in TC. Then each of the next M lines will have two integers, describing the two stations that a certain railway is connecting. After this, there comes a line containing a single integer Q (Q<=300000), which means the number of queries to make on the system. The next Q lines will be queries. Each query begins with a integer, indicating the type of query, followed by 4 (the first type) or 3 (the second type) integers describing the details of the query as what mentioned above.
The stations are always labeled from 1 to N.

输出:

For each test case, the first line will contain two integers N (2<=N<=100000) and M (1<=M<=500000), namely the number of stations and railways in TC. Then each of the next M lines will have two integers, describing the two stations that a certain railway is connecting. After this, there comes a line containing a single integer Q (Q<=300000), which means the number of queries to make on the system. The next Q lines will be queries. Each query begins with a integer, indicating the type of query, followed by 4 (the first type) or 3 (the second type) integers describing the details of the query as what mentioned above.
The stations are always labeled from 1 to N.

样例输入:

13 15
1 2
2 3
3 5
2 4
4 6
2 6
1 4
1 7
7 8
7 9
7 10
8 11
8 12
9 12
12 13
5
1 5 13 1 2
1 6 2 1 4
1 13 6 7 8
2 13 6 7
2 13 6 8

样例输出:

yes
yes
yes
no
yes

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<list>
#include<cctype>
#include<ctime>
#include<algorithm>
using namespace std;

#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define inf -1u>>1
#define MP(x,y) make_pair(x,y)
#define two(x) (1<<x)
#define eps 1e-8
const double pi=acos(-1.0);

/***************By Asakura*****************/
#define N 100005
#define M 500005
struct edge{
 int v;
 int next;
 int vis;
}ee[M*2];
int n,m,root,low[N],dfn[N],p[N],leave[N],deep[N],tot,cnt;
int dp[25][N];
void init()
{
 tot=0;
 cnt=0;
 memset(p,-1,sizeof(p));
 memset(dfn,0,sizeof(dfn));
 memset(low,0,sizeof(low));
 memset(dp,-1,sizeof(dp));
 memset(deep,-1,sizeof(deep));
 memset(leave,-1,sizeof(leave));
}
void add(int u,int v)
{
 ee[cnt].v=v;ee[cnt].next=p[u];ee[cnt].vis=0;
 p[u]=cnt++;
 ee[cnt].v=u;ee[cnt].next=p[v];ee[cnt].vis=0;
 p[v]=cnt++;
}
void dfs(int u,int dep)
{
 dfn[u]=low[u]=++tot;
 deep[u]=dep;
 int i;
 for(i=p[u];~i;i=ee[i].next)
 {
 if(ee[i].vis)continue;
 ee[i].vis=ee[i^1].vis=1;
 int v=ee[i].v;
 if(!dfn[v])
 {
 dfs(v,dep+1);
 low[u]=min(low[u],low[v]);
 dp[1][v]=u;
 }
 else
 low[u]=min(low[u],dfn[v]);
 }
 leave[u]=tot;
}
void tarjan()
{
 int i,j;
 for(i=1;i<=n;i++)
 if(!dfn[i])
 dfs(i,0);
 for(i=2;i<20;i++)
 for(j=1;j<=n;j++)
 if(dp[i-1][j]!=-1)
 dp[i][j]=dp[i-1][dp[i-1][j]];
}
bool s_tree(int x,int root)
{
 if(dfn[x]>=dfn[root]&&leave[x]<=leave[root])
 return true;
 return false;
}
int find(int x,int sp)
{
 int i,cnt=1,t=x;
 if(sp<0)
 return -1;
 while(sp)
 {
 if(sp&1)
 t=dp[cnt][t];
 cnt++;
 sp>>=1;
 }
 return t;
}
bool judgeE(int s,int t,int u,int v)
{
 if(deep[u]<deep[v])
 swap(u,v);
 bool flag=0;
 bool f1=s_tree(s,u);
 bool f2=s_tree(t,u);
 if(!f1&&!f2)
 flag=1;
 else if(f1&&f2)
 flag=1;
 else if(f1^f2&&low[u]<=dfn[v])
 flag=1;
 return flag;
}
bool judgeV(int s,int t,int u)
{
 bool f1=s_tree(s,u);
 bool f2=s_tree(t,u);
 bool flag=0;
 int tmd1,tmd2;
 if(!f1&&!f2)
 flag=1;
 else if(f1&&!f2)
 {
 tmd1=find(s,deep[s]-deep[u]-1);
 if(low[tmd1]<dfn[u]&&tmd1!=-1)
 flag=1;
 }
 else if(!f1&&f2)
 {
 tmd2=find(t,deep[t]-deep[u]-1);
 if(low[tmd2]<dfn[u]&&tmd2!=-1)
 flag=1;
 }
 else
 {
 tmd1=find(s,deep[s]-deep[u]-1);
 tmd2=find(t,deep[t]-deep[u]-1);
 if(tmd1==tmd2)
 flag=1;
 else if(low[tmd1]<dfn[u]&&low[tmd2]<dfn[u])
 flag=1;
 }
 return flag;
}
int main()
{
 int u,v,q,type,s,t,a,b,i;
 while(scanf("%d%d",&n,&m)!=EOF)
 {
 init();
 for(i=1;i<=m;i++)
 {
 scanf("%d%d",&u,&v);
 add(u,v);
 }
 tarjan();
 scanf("%d",&q);
 while(q--)
 {
 scanf("%d",&type);
 if(type==1)
 {
 scanf("%d%d%d%d",&s,&t,&u,&v);
 if(judgeE(s,t,u,v))
 puts("yes");
 else
 puts("no");
 }
 else
 {
 scanf("%d%d%d",&s,&t,&u);
 if(judgeV(s,t,u))
 puts("yes");
 else
 puts("no");
 }
 }
 }
 return 0;
}

  1. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。

  2. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!

  3. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience