雅礼集训1.4 轰炸

Posted by yjjr's blog on January 1, 2018

标签:tarjan缩点,拓扑排序,DP

题目

轰炸(bomb)

【题目描述】

有n座城市,城市之间建立了m条有向的地下通道。

你需要发起若干轮轰炸,每轮可以轰炸任意多个城市。但每次轰炸的城市中,不能存在两个不同的城市i,j满足可以通过地道从城市i到达城市j。

你需要求出最少需要多少轮可以对每座城市都进行至少一次轰炸。

【输入数据】

第一行两个整数n,m。接下来m行每行两个整数a,b表示一条从a连向b的单向边。

【输出数据】

一行一个整数表示答案。

【样例输入】

5 4

1 2

2 3

3 1

4 5

【样例输出】

3

【数据范围】

对于20%的数据,n,m<=10。

对于40%的数据,n,m<=1000。

对于另外30%的数据,保证无环。

对于100%的数据,n,m<=1000000。

分析

唔,感觉这题noip难度,全世界都A了这题

先将原图tarjan缩点,重构图,转化为求最长链

容易发现将一个大小为x的强连通分量替换成一个长度为x的链,所有点两两之间的连通关系不变。

然后按拓扑序DP即可

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define newreg(x) for(int i=rlast[x];i;i=re[i].next)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

const int maxn=1e6+6,maxm=2e6+6;
int dfn[maxn],low[maxn],que[maxn<<1],d[maxn],last[maxn],rlast[maxn],time=0,top,cnt=0,tot;
int belong[maxn],v[maxn],n,m;
int f[maxn],ans=0;
bool inq[maxn];
struct edge{int to,next;}e[maxm<<1],re[maxm<<1]; 
queue <int> q;
void tarjan(int x){
	int now=0;
	dfn[x]=low[x]=++time;
	que[++top]=x;inq[x]=1;
	reg(x)
		if(!dfn[e[i].to]){tarjan(e[i].to);low[x]=min(low[x],low[e[i].to]);}
		else if(inq[e[i].to])low[x]=min(low[x],dfn[e[i].to]);
	if(low[x]==dfn[x]){
		tot++;
		while(now!=x){
			now=que[top--];
			belong[now]=tot;
			v[tot]++;
			inq[now]=0;
		}
	}
}

void rebuild(){
	cnt=0;
	rep(k,1,n)
		reg(k)
			if(belong[e[i].to]!=belong[k]){
				re[++cnt]=(edge){belong[e[i].to],rlast[belong[k]]};rlast[belong[k]]=cnt;d[belong[e[i].to]]++;
			}
}
		
int main()
{
	n=read(),m=read();
	rep(i,1,m){
		int u=read(),v=read();
		e[++cnt]=(edge){v,last[u]};last[u]=cnt;
	}
	rep(i,1,n)if(!dfn[i])tarjan(i);//cout<<"R";
	rebuild();
	//rep(i,1,n)cout<<belong[i]<<' ';cout<<endl; 
	//rep(i,1,tot)cout<<d[i]<<' '<<v[i]<<endl;cout<<"E\n";
	rep(i,1,tot)if(d[i]==0)q.push(i);
	while(!q.empty()){
		int now=q.front();q.pop();
		f[now]+=v[now];
		ans=max(ans,f[now]);
		newreg(now){
			f[re[i].to]=max(f[re[i].to],f[now]);
			d[re[i].to]--;if(!d[re[i].to])q.push(re[i].to);
		}
	}
	cout<<ans<<endl;
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr