点击蓝字
关注赵码匠
（1）平衡路线
给定一个张有n个顶点、m条边的无向图，每条边带有符号+或-。对于一条从顶点s到顶点t的路线，允许重复经过顶点和边，定义一条路线的权值如下：记 
分别为经过的+边数和经过的-边数，则该路线的权值为
。
请计算从s到t的路线的最小权值。若不存在从s到t的路线，则输出-1。
输入第一行为4个整数n,m,s,t。接下来m行，每行给出两个整数a,b和一个字符+或-，描述一条连接a与b的无向边及其符号。
数据满足2≤n≤2×10^5，1≤m≤4×10^5，1≤s,t≤n且s≠t，1≤a,b≤n，可能出现重边。
以下程序通过BFS求出最小权值，请补全程序。
为了不让考生很容易地猜测数据的功能，现在CCF在出题时，给数组名称起的特别简单，但是凭借日常训练的经验，我们可以推测本题几乎所有数据的含义。
（1）第10～15行的代码为标准的链式前向星存储图结构的模板代码，因此idx为边的序号+边总数，h[i]数组存储链的头节点下标，e[i]存储第i条边的终点，ne[i]存储与第i条边相同起点的下一条边的序号，w[i]存储第i条边的权值。
由于图为无向图，每条边需要正向和反向存储两遍，因此e[]、ne[]、w[]这三个存储边的数组都要开2倍大小，即“*2”或“<<1”。
（2）题干明确了算法为“BFS”广度优先搜索，因此需要数据结构——队列来模拟搜索过程，根据第34行获取队头的代码，可以确定q[]数组用来模拟队列进行BFS；
（3）本题为特殊的单源最短路径问题，那么代码中熟悉的d[i]数组，就表示从起点s到达节点i的最短路径，但是是路径长度还是权值之和尚未可知。
最后，就剩c[]数组不知道其功能，我们先去阅读程序的算法设计逻辑，在做题中逐步分析其含义。
34、①处应填（ ）
A、op[0] == '+' ? 0 : 1
B、op[0] == '+'
C、op[0] == '+' ? 1 : -1
D、op[0] == '-' ? 1 : 0
答案：C
解析：这一空在进行图结构的边的读入，根据题干读入每条边的a、b和正负号，但是代码中将正负号读进了字符数组op[2]中；
如果只用“char op;”，并且在字符后续还有多余的空格、换行等，读取单个字符后并不会跳过这些，可能会导致后续输入出现错误；
而定义op[2]后，不仅可以防止这些特殊情况，并且在输出时，可以直接用”cout<<op”来将字符打印出来，如果cout字符变量则默认为对应的ASCII码，需要转换。
回到题目中来，在字符串op中，第一个字符为+或-，第二个字符为'\0'，我们需要的是判断当前边的符号是+还是-，因此要读取op[0]里的值；
结合路线权值的计算规则：遇到符号+，路线权值增加1，遇到符号-，路径权值减少1，对应正确的逻辑判断描述仅为选项C。
35、②处应填（ ）
A、hh < n
B、tt < n
C、hh <= tt
D、hh < tt
答案：D
解析：这里填写BFS中队列非空判断，即用数组模拟队列时，什么条件语句等价于q.empty()。
观察29~32行在BFS前对起点的处理，可以发现hh是队列头指针，tt是队列尾指针，因此当hh>=tt时队列为空，那么反过来hh<tt时就要继续搜索，对应为选项D。
36、③处应填（ ）
A、d[y] + 1
B、d[x] + 1
C、d[x]
D、d[x] - 1
答案：B
解析：继续阅读BFS的代码：
（1）第34行代码取出当前队头节点x；
（2）第35行，遍历队头节点的所有相邻节点；
（3）第36行的y为邻接点y，第37~38行根据这条边的正负情况，如果正数让p=1，负数则让ng=1；
（4）第39~42行的判断，d[y]==-1表示当前节点y还未访问，此时更新到达节点y的路径长度为先到达x再+1，对应答案为选项B。
这里可能有读者会有疑问：为什么不是+w[i]而是+1呢？这就和第5题的输出有关了，具体分析请于第5题结合，这里直接给出答案：d[i]记录的是从起点到i的路径长度，而不是权值之和。
37、④处应填（ ）
A、c[y] == c[x]
B、w[i] == 1
C、c[y] != c[x]
D、d[y] + 1 != d[x]
答案：A
解析：首先在第41行设计了代码“c[y]=c[x]^1;”，这句代码让节点x的值与节点y的值不同，属于二分图的核心代码。
二分图指的是图中所有顶点可以分成两个独立的子集，任一子集中的任意顶点之间没有边连接，一般通过染色法来实现，也就是本题的c[i]数组，让相邻两个结点的颜色不同。
假设两个结点c[i]=c[j]颜色相同，说明从i到j的路径是偶数，反之则是奇数，路径奇偶性的判断，与最终输出的结果有关，简而言之是偶数输出0，奇数输出1。
在BFS中，对于没有访问过的节点y，直接将其标记为与x相反的颜色；
对于访问过的节点y，需要与邻居x的颜色进行判断，如果c[x]==x[y]，表明该图不是二分图，对应为选项A。
那么，二分图与本题的答案有什么关系呢？
如果图为二分图，那么从起点s到终点t的所有路径的奇偶性都是一样的，如果是偶数则路径权值为0，如果是奇数则路径权值为1；
如果图不为二分图，那么图中肯定存在一个环（或者重复走同一条路径），可以让路径权值稳定增加或减少，这时候可以通过反复“刷”这个环的路来实现将路径权值调整到0。
38、⑤处应填（ ）
A、ok && c[s] == c[t]
B、ok && c[s] != c[t]
C、!ok || c[s] == c[t]
D、!ok && c[s] != c[t]
答案：C
解析：第47~56行在分情况进行输出：
（1）d[t]=-1表示不存在路线，返回-1；
（2）“!p || !ng”结合BFS中代码来看，用于标记是否存在符号为+或-的边，其中这两个变量假如有1个为0，说明边的符号都是+或-，此时的最小权值就是对应路径的长度，因此直接输出d[t]即可；
从这里可以确定，数组d[i]的含义为记录从起点s到i的路径长度。
（3）最后就是边符号有+有-的情况，这时候结合题干中的重要信息“可能出现重边”，可以将路径分为两种情况：
·存在一个环，使得可以在该环上反复走来减小或增加权值；
如果存在这样的环，那么必定存在一种方案，可以将权值绕为0（因为权值是绝对值，因此最小值肯定是0）；
·不存在上述的环，正常走；
如果路径长度是偶数，那肯定可以通过调整路径（例如重复走多次同一条边等），让最终的权值为0;
程序中，判断是否存在这样的环对应的标记变量为ok，ok=1表示存在这样的环；
路径长度为偶数对应的判断为d[t] % 2 == 0，但是选项中没有，这里就要进行转换了：
假设路径长度为偶数，那么起点和终点的“01”情况是相同的，即起点和终点颜色相同，因此可以等价转换为c[s]==c[t]。
两种情况有一个满足即可，对应正确的判断是选项C。
原创文章制作不易
欢迎大家分享到微信群、朋友圈等社交圈
如需转载，可后台留言开通白名单
注：未经允许不得私自搬运到其他平台
如果觉得写的不错的话
还请帮忙点赞、在看、关注
谢谢!
