夏晓光(loveJY)的博客

仍要向下扎根,向上结果

首页 归档 标签 关于 友链

某金牌训练营Day2

2021-02-17 10 min read

A. 次短路径

首先我们知道每个点到1号点最短路的第一条边是确定的,那么你会发现其实就是所有最短路都是确定的

也就是最短路树是唯一的

然后我的想法是对于每条边,如果是横叉边,就直接走过去,然后用对面那个点的最短路去解决

否则如果是返祖边,我们可能因为走了这条边而导致最短路还需要经过标记边,不能直接统计

考虑将第一种情况推广,此时我们应该是走非树边再走一条边走出u的子树然后走回根1号点,那么也就是说我们应该是沿着树边走到子树内某个点,然后横叉边

因为如果不走树边走过去更优,说明我们有更好的选择,而因为最短路树是唯一的,所以我们不可能有更好的选择

这个横叉边之后的部分很好统计,对于其余的走过去的部分的路径,我们可以使用线段树合并,支持全局加然后合并查询全局最小值即可

注意点u直接连出去的横叉边

两个堆删除特定值,直接存入另一个堆,然后每次取出堆顶比较一下即可

注意我们一个边只会对于(u,v)(u,v)两对点产生贡献

注意开longlong1坑死了

最后写了最好写的启发式合并/ll

#include<bits/stdc++.h>
#define pi pair<int,int>
#define int long long
#define ps push
#define pb push_back
#define fi first
#define se second
#define mkp(x,y) (make_pair(x,y))
#define vi vector<int>
using namespace std;
const int MAXN = 5e5 + 7;

int n, m, ccnt, ccnt2;
int home[MAXN], nxt[MAXN], to[MAXN], w[MAXN], tag[MAXN], ans[MAXN], frm[MAXN];
int fst[MAXN], tto[MAXN], len[MAXN], nxtt[MAXN];

inline void ct(int x, int y, int z) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
	w[ccnt] = z;
	frm[ccnt] = x;
}

priority_queue<pi, vector<pi>, greater<pi> > heap;
int dis[MAXN], pre[MAXN], vis[MAXN], prep[MAXN];

inline void ct2(int x, int y, int z) {
	ccnt2++;
	nxtt[ccnt2] = fst[x];
	fst[x] = ccnt2;
	tto[ccnt2] = y;
	len[ccnt2] = z;
}

inline void dijkstra(int s) {
	memset(dis, 0x3f3f3f3f, sizeof(dis));
	dis[s] = 0;
	heap.ps(mkp(0, s));
	while(!heap.empty()) {
		int u = heap.top().se;
		heap.pop();
		if(vis[u])continue;
		vis[u] = 1;
		for(int i = home[u]; i; i = nxt[i]) {
			int v = to[i];
			if(dis[v] > dis[u] + w[i]) {
				dis[v] = dis[u] + w[i];
				pre[v] = u;
				prep[v] = w[i];
				heap.ps(mkp(dis[v], v));
			}
		}
	}
	for(int i = 1; i <= n; ++i) {
		if(pre[i])ct2(pre[i], i, prep[i]);
	}
	return ;
}

int siz[MAXN], son[MAXN], dep[MAXN], top[MAXN], dfn[MAXN], depp, mx[MAXN];

inline void dfs1(int u, int depth) {
	dfn[u] = ++depp;
	mx[u] = dfn[u];
	siz[u] = 1;
	dep[u] = depth;
	for(int i = fst[u]; i; i = nxtt[i]) {
		int v = tto[i];
		if(v == pre[u])continue;
		dfs1(v, depth + 1);
		siz[u] += siz[v];
		mx[u] = max(mx[v], mx[u]);
		if(siz[v] > siz[son[u]])son[u] = v;
	}
	return ;
}

inline void dfs2(int u, int topf) {
	top[u] = topf;
	if(!son[u])return ;
	dfs2(son[u], topf);
	for(int i = fst[u]; i; i = nxtt[i]) {
		int v = tto[i];
		if(v == pre[u])continue;
		dfs2(v, v);
	}
	return ;
}

inline void init() {
	dfs1(1, 0);
	memset(ans, -1, sizeof(ans));
	return ;
}

priority_queue<pi, vector<pi>, greater<pi> > hp[MAXN];

inline int pd(int u, int i) {
	if(dfn[frm[i]] >= dfn[u] && dfn[frm[i]] <= mx[u] && dfn[to[i]] >= dfn[u] && dfn[to[i]] <= mx[u])return 0;
	return 1;
}

inline void dfs(int u) {
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if((dfn[v] >= dfn[u] && dfn[v] <= mx[u]) || v == pre[u])continue;
		hp[u].ps(mkp(w[i] + dis[v], i));//标记这条边
	}
	for(int i = fst[u]; i; i = nxtt[i]) {
		int v = tto[i];
		if(v == pre[u])continue;
		dfs(v);
		if(hp[v].size() > hp[u].size()) {
			swap(hp[v], hp[u]);
			swap(tag[u], tag[v]);
			while(!hp[v].empty()) {
				pi g = hp[v].top();
				g.fi += -len[i] + tag[v] - tag[u];
				hp[u].ps(g);
				hp[v].pop();
			}
			tag[u] += len[i];
		} else while(!hp[v].empty()) {
				pi g = hp[v].top();
				g.fi += len[i] + tag[v] - tag[u]; //被迫延长
				hp[u].ps(g);
				hp[v].pop();
			}
	}//poly log
	while(!hp[u].empty()) {
		pi g = hp[u].top();
		g.fi += tag[u];
		if(pd(u, g.se)) {
			ans[u] = g.fi;
			break;
		}
		hp[u].pop();
	}
	return ;
}

signed main() {
	freopen("pal.in", "r", stdin);
	freopen("pal.out", "w", stdout);
	scanf("%lld%lld", &n, &m);
	for(int i = 1, x, y, z; i <= m; ++i) {
		scanf("%lld%lld%lld", &x, &y, &z);
		ct(x, y, z);
		ct(y, x, z);
	}
	dijkstra(1);//建树
	init();//直接tag上
	dfs(1);//线段树合并
	for(int i = 2; i <= n; ++i)printf("%lld\n", ans[i]);
	return 0;
}

B. 带权的图

不阳间,没想

建议dfs树,会发现一个环两条边走两遍没有意义的

然后我们找到环,就是几条返祖边和树边构成的

然后我们发现一个环对应的其他环,(只经过了一返祖边拼成)把这些环找出来

这个环可以由那些环的加和拼起来,因为我们说过走了多遍的一定没用,而这个情况下只有树边会被经过多次而被消掉

也就是说,我们求出的C只需要满足dfs树上简单环(一条返祖边构成)的限制即可

然后再思考我们求得是C,同时有

∑B∗C=∑A\sum B*C= \sum A

这个形式可以得到m−n+1m-n+1个方程,每个环和树边组成的方程

然后这些方程直接高斯消元还不太够,我们再利用上对于一个点满足C的和为0这个条件,就有足够多的方程了,这样就能消得所有的边

这个复杂度是O(m3)O(m^3)

考虑为什么太慢了,因为我们的变量数太多了

定义变量D(u,v)=B∗C(u,v)−A(u,v)D(u,v)=B*C(u,v)-A(u,v)

那么我们就有一个环的D和为0,因为我们一个环满足上述条件3啊

那么我们一定能把环拆成两部分,满足两条路径的边权和为相反数

然后,对于任意两条从u到v的路径,他们的D权值和一定是一样的

因为如果不一样,说明我们把这两条路径拿出来组成环,这个环的权值和不是0

所以从1号点出发走到u号点的权值为ϕu\phi u,对于边(u,v)(u,v)就有D(u,v)=ϕv−ϕuD(u,v)=\phi v-\phi u

发现实际上我们是使用了第三个限制条件

根据第二个条件,先让ϕ1=0\phi 1=0

有

∑(u,v)ϕ(v)−ϕ(u)+A(u,v)B(u,v)=0\sum_{(u,v)} \frac{\phi(v)-\phi(u)+A(u,v)}{B(u,v)}=0

直接对于这个方程高斯消元即可,其中(u,v)是所有u的出边

C. 木棍问题

首先黑白染色建立费用流模型

然后我们网格中的点强制由黑点连向白点

如果流量是一个特定值表示放入多少木棍,那由费用可以直接求出答案了

当A=B的时候,我们每个木球流量只和度数有关系

然后我们直接连重边然后差分就好了,在费用流增广我们会优先使用最短路

然后注意白点要有流量限制为4,不能有度数大于4的点,白点也要向T连四种边,要不然就少算了...

如果B>AB>A,我们要使用这个条件啊!

此时相当于有(B−A)+A(B-A)+A额外费用

最多只会有两种这样的情况,第一种是横向的三个球,第二种是纵向三个球

所以拆点,我们一个点拆出三个点,一个点先向拆出的x1x_1,然后连4个A的边,就是第一步的差分的边

然后再向横向和纵向的两个点,流出一个是(1,0),(1,B−A)(1,0),(1,B-A)另一个也是(1,0)(1,B−A)(1,0)(1,B-A)的边即可

这样你发现我们一定会优先(1,0)(1,0),第二次在选择这个方向就是(1,B−A)(1,B-A)

实现的时候用zkw费用流加速,然后每次我们虽然可以增加很多流量,这些流量并不需要一点点加,同时推给答案数组即可

633. 「左偏树」逃跑计划

考虑以1为根

然后1到t的重链,上面有一些子树

Powered by Gridea RSS