【Codeforces 757F】Team Rocket Rises Again

相关链接

题目传送门:http://codeforces.com/problemset/problem/757/F
官方题解:http://codeforces.com/blog/entry/49743
中文题面及题解:https://blog.sengxian.com/solutions/cf-757f

解题报告

先搞出一个最短路径树,然后把一些非树边也给搞进来
我们发现这货是一个DAG,那么问题就转化为了:

给定一个DAG,问删掉一个点,最多使得多少点不可到达

然后我们就会想起这个题:BZOJ 2851
于是我们搞一个灾难树就可以啦!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200000+9;
const int M = 600000+9;
const LL INF = 1e9 * 1e9;

LL dis[N];
int n,m,s,E,vout,fa[N][20],done[N],in[N];
int head[N],to[M],nxt[M],cost[M],dep[N]; 
priority_queue<pair<LL,int> > que;
vector<int> anc[N],son[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void Add_Edge(int u, int v, int c = 0) {
	to[++E] = v; nxt[E] = head[u]; head[u] = E; cost[E] = c;
	to[++E] = u; nxt[E] = head[v]; head[v] = E; cost[E] = c;
}

inline void Dijkstra() {
	memset(dis,60,sizeof(dis)); 
	dis[s] = 0; que.push(make_pair(0, s));
	
	while (!que.empty()) {
		int w = que.top().second; que.pop(); 
		if (!done[w]) done[w] = 1;
		else continue;
		for (int i=head[w];i;i=nxt[i]) {
			if (dis[to[i]] > dis[w] + cost[i]) {
				dis[to[i]] = dis[w] + cost[i];
				que.push(make_pair(-dis[to[i]], to[i]));
			}
		}
	}
}

inline int LCA(int u, int v) {
	if (dep[u] < dep[v]) swap(u, v);
	for (int i=19;~i;i--) if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];
	if (u == v) return u;
	for (int i=19;~i;i--) if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
	return fa[u][0];
}

void solve(int w) {
	done[w] = 1;
	int f = anc[w][0];
	for (int i=1;i<(int)anc[w].size();i++) 
		f = LCA(f, anc[w][i]);
	Add_Edge(f, w);
	fa[w][0] = f; dep[w] = dep[f] + 1;
	for (int i=1;i<20;i++)
		fa[w][i] = fa[fa[w][i-1]][i-1];
	for (int i=son[w].size()-1,t;~i;i--) {
		t = son[w][i];
		if (--in[t] == 0 && !done[t]) {
			solve(t);
		}
	}
}

int DFS(int w, int f) {
	int sz = 1;
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			sz += DFS(to[i], w);
		}
	}
	if (w != s) vout = max(vout, sz);
	return sz;
}

int main() {
	n = read(); m = read(); s = read();
	for (int i=1,u,v;i<=m;i++) {
		u = read(); v = read();
		Add_Edge(u, v, read());
	}
	Dijkstra(); 
	for (int w=1;w<=n;w++) {
		if (dis[w] > INF) continue;
		for (int i=head[w];i;i=nxt[i]) {
			if (dis[to[i]] == dis[w] + cost[i]) {
				anc[to[i]].push_back(w);
				son[w].push_back(to[i]);
				in[to[i]] += (w != s);
			}
		}
	}
	memset(head,0,sizeof(head));
	memset(done,0,sizeof(done));
	done[s] = 1; E = 0;
	for (int i=0;i<20;i++) fa[s][i] = s;
	for (int i=1;i<=n;i++) {
		if (!in[i] && !done[i] && dis[i] < INF) {
			solve(i);
		}
	}
	DFS(s, s);
	printf("%d\n",vout);
	return 0;
}

【BZOJ 2851】极限满月

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2851
数据生成器:http://paste.ubuntu.com/23321973/

这道题我真的是服了。 服气!
0_7uftv1i06u7jhr9

如果考虑{ai}为父亲集合的话
这货是个DAG
然后看一看{bi}中涉及到的∩操作
从顶端向下考虑的话,这™不就是支配点!
于是求一求灾难树,然后求一求路径并

话说这么巧妙的题目出题人是怎么想到的!
服! 真心服!

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200000+9;
const int M = N*200;

int head[N],nxt[M],to[M],n,m,in[N],out[N];
int que[N],fa[N][18],dep[N],num_cnt;
vector<int> G[N];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void Add_Edge(int u, int v) {
	static int T = 0; in[v]++;
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
}

inline bool cmp(const int &a, const int &b) {
	return in[a] < in[b];
}

inline int lca(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	for (int i=17;~i;i--) {
		if (dep[fa[x][i]] >= dep[y]) {
			x = fa[x][i];
		}
	}	
	if (x == y) return y;
	for (int i=17;~i;i--) {
		if (fa[x][i] != fa[y][i]) {
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	return fa[x][0];
}

inline void solve(int w) {
	dep[w] = dep[fa[w][0]] + 1;
	if (w) G[fa[w][0]].push_back(w);
	for (int i=1;i<=17;i++) {
		fa[w][i] = fa[fa[w][i-1]][i-1];
	}
	
	for (int i=head[w];i;i=nxt[i]) {
		if (!~fa[to[i]][0]) {
			fa[to[i]][0] = w;
		} else {
			fa[to[i]][0] = lca(fa[to[i]][0], w);
		}
		
		if (!--in[to[i]]) solve(to[i]);
	}
}

void DFS(int w) {
	in[w] = ++num_cnt;
	for (int i=G[w].size()-1;~i;i--) {
		DFS(G[w][i]);
	}
	out[w] = num_cnt;
}

int main(){
	memset(fa,-1,sizeof(fa));
	n = read();
	for (int i=1;i<=n;i++) {
		for (int j=read();j;j--) {
			Add_Edge(read(),i);
		}
		if (!in[i]) {
			Add_Edge(0,i);
		}
	}
	
	fa[0][0] = 0;
	solve(0);
	DFS(0);
	
	m = read(); 
	for (int k=1,len,vout=0;k<=m;k++,vout=0) {
		len = read();
		for (int j=1;j<=len;j++) {
			que[j] = read();
		}
		
		sort(que+1,que+1+len,cmp);
		for (int i=1,pre=0;i<=len;i++) {
			vout += dep[que[i]];
			vout -= dep[lca(pre,que[i])];
			pre = que[i];
		}
		
		printf("%d\n",vout);
	}
	return 0;
}

—– UPD 2016.10.16 —–
今天发现这题数据范围有问题
关系数应该是小于2e6
点数应该是小于2e5

【BZOJ 2815】[ZJOI2012] 灾难

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2815
题面传送门:http://blog.csdn.net/flaze_/article/details/51334708

这题好好玩!
让我们来膜拜fanhq666:
http://fanhq666.blog.163.com/blog/static/8194342620124274154996/

这题把数学模型抽象出来就是:
给一个有向无环图,问每个节点删掉之后会导致多少个点不可达。
感觉还是挺有用的样子!

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100000;
const int M = 1000000;

int head[N],to[M],nxt[M],fa[N][18];
int in[N],sz[N],dep[N],n; 
vector<int> G[N];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void Add_Edge(int u, int v) {
	static int T = 0; in[v]++;
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
}

inline int lca(int x, int y) {
	if (dep[x] < dep[y]) swap(x,y);
	for (int i=17;~i;i--) {
		if (dep[fa[x][i]] >= dep[y]) {
			x = fa[x][i];
		}
	}
	if (x == y) return y;
	for (int i=17;~i;i--) {
		if (fa[x][i] != fa[y][i]) {
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	return fa[x][0];
}

void solve(int w) {
	dep[w] = dep[fa[w][0]] + 1;
	if (w) G[fa[w][0]].push_back(w);
	for (int i=1;i<=17;i++) {
		fa[w][i] = fa[fa[w][i-1]][i-1];
	}
	
	for (int i=head[w];i;i=nxt[i]) {
		if (fa[to[i]][0] == -1) {
			fa[to[i]][0] = w;
		} else {
			fa[to[i]][0] = lca(fa[to[i]][0],w);
		}
		
		if (--in[to[i]] == 0) {
			solve(to[i]);
		}
	}
}

void Get_Size(int w) {
	sz[w] = 1;
	for (int i=G[w].size()-1;~i;i--) {
		Get_Size(G[w][i]);
		sz[w] += sz[G[w][i]];
	}
}

int main(){
	memset(fa,-1,sizeof(fa));
	n = read();
	for (int i=1;i<=n;i++) {
		for (int j=read();j;j=read()) {
			Add_Edge(j,i);
		}
		if (!in[i]) {
			Add_Edge(0,i);
		}
	}
	
	fa[0][0] = 0;
	solve(0);
	Get_Size(0);
	
	for (int i=1;i<=n;i++) {
		printf("%d\n",sz[i] - 1);
	}
	return 0;
}