“蔚来杯“2022牛客暑期多校训练营9 C题: Global Positioning System

C题: Global Positioning System

原题链接:https://ac.nowcoder.com/acm/contest/33194/C

题目大意

三维空间中彼此相对静止的 $n(2\le n\le 500000)$ 个点，有 $m(n-1\le m\le 500000)$ 条记录，第 $i$ 条记录表示第 $u_i$ 个点与第 $v_i$ 个点的坐标坐标差为 $(x_i,y_i,z_i)$ ，保证用已有的数据可以求出任意两点间的坐标差。

这些记录中，有恰好 $1$ 条记录是错的。定义一条记录是错的，当且仅当将该条记录的坐标差修改为其他值后，所有记录相互匹配吻合。

求所有可能的错误记录。

题解

将题意抽象为图，用边来称呼每一条数据(坐标差)，因为"保证用已有的数据可以求出任意两点间的坐标差"，所以原图为一张联通图。
当一个环上的坐标差和不为 $0$ 时，该环上的边可能是错误的。
如果没有错误的环，那么这张图中所有的桥(除去那些正确的环)都可能是错误的。
如果有多个错误的环，那么只有它们的交才可能是错误的。
可以用 $Tarjan$ 算法求出该图的一棵 $dfs$ 树(在此过程中可以求出所有的桥)，每次遇到一条返祖边时即找到一个环，判断环的正确性，对环上的点标记即可(在 $dfs$ 树上的边通过树上差分标记，返祖边单独标记)。
然后求出最多的标记数，持有该标记数的边都是可能错误的。

参考代码

#include
using namespace std;

template<class T>inline void read(T&x){
	char c,last=' ';
	while(!isdigit(c=getchar()))last=c;
	x=c^48;
	while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+(c^48);
	if(last=='-')x=-x;
}

#define LL long long
const int MAXN=5e5+7;
int n,m,tot;
vector<int>bridges;//保存桥
struct node{//记录边的数据(坐标差),也用于统计坐标差的和
	LL x,y,z;
	node(LL X,LL Y,LL Z):x(X),y(Y),z(Z){}
	node(){}
}v[MAXN];
LL d[MAXN];//差分在点上的标记
LL t[MAXN];//对边的标记
vector<node>E;//总边集
vector<pair<int,int> >e[MAXN];//每个点的边集,存通向的点和数据的编号
int dfn[MAXN],low[MAXN];//Tarjan

node operator+(const node&a,const node&b){
	return node(a.x+b.x,a.y+b.y,a.z+b.z);
}

bool operator==(const node&a,const node&b){
	return a.x==b.x&&a.y==b.y&&a.z==b.z;
}

void addedge(int u,int v,int x,int y,int z){//双向建边
	e[u].push_back(make_pair(v,E.size()));E.push_back(node(x,y,z));
	e[v].push_back(make_pair(u,E.size()));E.push_back(node(-x,-y,-z));//注意取相反数
}

void dfs(int x,int fa){
	dfn[x]=low[x]=++tot;
	for(int i=0,son;i<e[x].size();++i){
		son=e[x][i].first;
		node w=E[e[x][i].second];
		if(son==fa)continue;
		if(!dfn[son]){//新的点
			v[son]=v[x]+w;//记录总坐标差
			dfs(son,x);
			low[x]=min(low[x],low[son]);
			t[e[x][i].second/2]+=d[son];//更新边的标记
			d[x]+=d[son];//传递标记
			if(dfn[x]<low[son])bridges.push_back(e[x][i].second/2);//找到桥
		}
		else if(dfn[son]<dfn[x]){//返祖边(找到环)
			low[x]=min(low[x],dfn[son]);
			if(v[x]+w==v[son]){//坐标差的和为0,环是正确的,全部标记减去无穷大,表示其不可能错误
				d[x]-=1e9,d[son]+=1e9;
				t[e[x][i].second/2]-=1e9;//双向建边时,同一条边的两个方向在除2后是相等的
			}
			else{//环是错误的,全部标记加1
				++d[x],--d[son];
				++t[e[x][i].second/2];
			}
		}
	}
}

int main()
{
	read(n),read(m);
	for(int i=1,u,v,x,y,z;i<=m;++i){
		read(u),read(v),read(x),read(y),read(z);
		addedge(u,v,x,y,z);
	}
	dfs(1,0);
	LL Mx=-0x3f3f3f3f3f3f3f3f;
	for(int i=0;i<m;++i)Mx=max(Mx,t[i]);//记录最大标记
	if(Mx<=0){//没有可能错误的边(环)
		cout<<bridges.size()<<'\n';
		sort(bridges.begin(),bridges.end());//输出桥的编号,记得排序
		for(int i=0;i<bridges.size();++i)cout<<bridges[i]+1<<" \n"[i+1==bridges.size()];
	}
	else{
		int ans=0;
		for(int i=0;i<m;++i)ans+=t[i]==Mx;//输出所有标记数最大的边
		cout<<ans<<'\n';
		for(int i=0;i<m;++i)if(t[i]==Mx)--ans,cout<<i+1<<" \n"[ans==0];
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90