Blow up the city
时间限制: 1 Sec 内存限制: 128 MB
题目描述
Country A and B are at war. Country A needs to organize transport teams to deliver supplies toward some command center cities.
In order to ensure the delivery works efficiently, all the roads in country A work only one direction. Therefore, map of country A can be regarded as DAG( Directed Acyclic Graph ). Command center cities only received supplies and not send out supplies.
Intelligence agency of country B is credibly informed that there will be two cities carrying out a critical transporting task in country A.
As long as **any** one of the two cities can not reach a command center city, the mission fails and country B will hold an enormous advantage. Therefore, country B plans to destroy one of the n cities in country A and all the roads directly connected. (If a city carrying out the task is also a command center city, it is possible to destroy the city to make the mission fail)
Now country B has made q hypotheses about the two cities carrying out the critical task.
Calculate the number of plan that makes the mission of country A fail.
输入
The first line contains a integer T (1≤T≤10), denoting the number of test cases.
In each test case, the first line are two integers n,m, denoting the number of cities and roads(1≤n≤100,000,1≤m≤200,000).
Then m lines follow, each with two integers u and v, which means there is a directed road from city u to v (1≤u,v≤n,u≠v).
The next line is a integer q, denoting the number of queries (1≤q≤100,000)
And then q lines follow, each with two integers a and b, which means the two cities carrying out the critical task are a and b (1≤a,b≤n,a≠b).
A city is a command center if and only if there is no road from it (its out degree is zero).
输出
For each query output a line with one integer, means the number of plan that makes the mission of country A fail.
样例输入
2
8 8
1 2
3 4
3 5
4 6
4 7
5 7
6 8
7 8
2
1 3
6 7
3 2
3 1
3 2
2
1 2
3 1
样例输出
4
3
2
2
题意：有一个DAG，求有多少方案，使得割掉图中一个点，图上特定两个点不能都到达出度为0的点。
思路：反向建边，连接超级源点到原图中出度为0的点。那么题目就变成了：有一个DAG，求有多少种方案，使得割掉图中一个点，从超级源点不能都到达两个特定点。这就是支配树问题。支配树是一个有向图抽象出来的树，它满足某一点到根节点的路径上的点，都是根结点在原图中到达这个点的必经点。
#include<bits/stdc++.h>
#define N 100005
using namespace std;
struct ss
{
int u,v,next;
};
ss edg[2*N];
int head[N],sum_edge=0;
void addedge(int u,int v)
{
edg[sum_edge]=(ss){u,v,head[u]};
head[u]=sum_edge++;
}
int grand[N][25]={0};
int depth[N],DEPTH;
void deal(int u,int v)
{
grand[v][0]=u;
depth[v]=depth[u]+1;
for(int i=1;i<=DEPTH;i++)
{
grand[v][i]=grand[grand[v][i-1]][i-1];
}
}
int lca(int a,int b)
{
if(a==0||b==0)return a+b;
if(depth[a]>depth[b])swap(a,b);
for(int i=DEPTH;i>=0;i--)
if(depth[a]<depth[b]&&depth[grand[b][i]]>=depth[a])b=grand[b][i];
for(int i=DEPTH;i>=0;i--)
if(grand[a][i]!=grand[b][i])
{
a=grand[a][i];
b=grand[b][i];
}
if(a!=b)
{
return grand[a][0];
}
return a;
}
void init(int n)
{
DEPTH=floor(log(n + 0.0) / log(2.0));
memset(grand[0],0,sizeof(grand[0]));
depth[0]=0;
sum_edge=0;
memset(head,-1,sizeof(head));
}
void getControl_tree(int n,int s)//从s出发可以到达图的所有点,s为支配树的根
{
int fa[N]={0};
int rd[N]={0};
stack<int>Stack;
for(int i=1;i<=n;i++)
for(int j=head[i];j!=-1;j=edg[j].next)rd[edg[j].v]++;
Stack.push(s);
while(!Stack.empty())
{
int x=Stack.top();
Stack.pop();
deal(fa[x],x);//建支配树
for(int i=head[x];i!=-1;i=edg[i].next)
{
int v=edg[i].v;
fa[v]=lca(fa[v],x);
rd[v]--;
if(!rd[v])Stack.push(v);
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m;
scanf("%d %d",&n,&m);
init(n);
int rd[N]={0};
while(m--)
{
int u,v;
scanf("%d %d",&u,&v);
addedge(v,u);
rd[u]++;
}
for(int i=1;i<=n;i++)if(!rd[i])addedge(n+1,i);
getControl_tree(n+1,n+1);
scanf("%d",&m);
while(m--)
{
int u,v;
scanf("%d %d",&u,&v);
int LCA=lca(u,v);
printf("%d\n",depth[u]+depth[v]-depth[LCA]-1-1+1);
}
}
return 0;
}
View Code支配树参考博客：https://www.cnblogs.com/fenghaoran/p/dominator_tree.html
Blow up the city
原文：https://www.cnblogs.com/tian-luo/p/11267123.html
