[Atcoder SoundHound Contest 2018]E.+ Graph

题面

Time limit : 2sec / Memory limit : 1024MB
Score : 600 points

Problem Statement-题目描述

Kenkoooo found a simple connected graph. The vertices are numbered $1$ through $n$. The $i$-th edge connects Vertex $u_i$ and $v_i$, and has a fixed integer $s_i$.
Kenkoooo is trying to write a positive integer in each vertex so that the following condition is satisfied:

For every edge $i$, the sum of the positive integers written in Vertex $u_i$ and $v_i$ is equal to $s_i$.

Find the number of such ways to write positive integers in the vertices.

Constraints-数据范围

$2\le n\le 10^5$
$1\le m\le 10^5$
$1\le u_i<v_i\le n$
$2\le s_i\le 10^9$
If $i?=j$, then $u_i?=u_j$ or $v_i?=v_j.$
The graph is connected.
All values in input are integers.

题目大意

给你一个无向图$G=(V,E)$,定义任意一条边$e=(i,j)$ $(i?=j,i\in V,j\in V)$的权值为$w_{i,j}$,任意一个点$c_i(c\in V)$的权值为$w_i$,且**$w_i$为正整数**,现在给出所有边$e$和边的权值$w_{i,j}$,求所有边与点都满足$w_{i,j}=w_i+w_j$时,1号结点有多少种不同的取值。
$2\le n\le 10^5$
$1\le m\le 10^5$
$1\le u_i<v_i\le n$
$2\le s_i\le 10^9$

题解

1.确定&方向

学过差分约束的同学可能会感觉这题与差分约束十分类似,是的。差分约束可以维护$a_i?a_j\le X$的情况,同时,$a_i?a_j=X$也可以转成$a_i?a_j\le X$进行差分约束。但题目的要求是$a_i+a_j=X$，至少在蒟蒻的知识范围内，是无法转化(或者很难转化)的。
这时候我们就又需要从暴力开始思考了。首先考虑枚举的变量应该是什么。
我们以样例2作为例子

4 3
1 2 6
2 3 7
3 4 5

显然我们可以将这些条件化成方程组
$$?\begin{array}{l}{a}_1+a_2=6\\ a_2+a_3=7\\ a_3+a_4=5\end{array}$$

我们很快可以发现只要我们知道其中的任意一个值，我们就可以求出所有的$a$。
我们不妨直接枚举$a_1$,判断它是否成立即可。
然而这样做一定是超时的，因此我们需要一个更好的方法来节省时间。
对方程比较敏感的同学很快会忍不住将$1,2$式相减得出$a_1?a_3=?1$,再将其与$3$式相加得出$a_1+a_4=4$。
这样一来，我们就求出$a_1$与其他$a$的关系。
但是这有何用呢。
再看看题目,题目要求$a_i>0$。显然我们需要往求范围的方向想问题。
因为$a2=6?a_1>0$,$a_3=a_1+1>0$,$a_4=4?a_1>0$。
我们就可以得到$a_1<6$,$a_1>?1$,$a_1<4$,和$a_1>0$结合得$0<a_1<4$即$a_1$有$3$个取值。没错，这就是正确答案了。
根据上面的操作我们可以发现几个有用的规律

1.当$n\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}2)$(即n%2=0)时,总有$a_1+a_n=A$,换成不等式即$a_1<A$。
2.当$n\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}2)$(即n%2=1)时,总有$a_1?a_n=B$,换成不等式即$a_1>B$。

显然，答案$a_1$的范围即为$\max (B_1,B_2,...,B_{k_1},0)<a_1<\min (A_1,A_2,...,A_{k_2})$
直接用$DFS/BFS$遍历整张图很容易求出范围与$a_1$的合法个数。
难道这就是这道题的正解？

2.尝试&完善

作为这场比赛的最后一题，绝对不可能这么简单。
上面的样例显然遗漏了我们的老朋友(233)——环。
这个关系在环上也成立吗?
让我们来看看第一组样例吧。

3 3
1 2 3
2 3 5
1 3 4

(莫名画成直角三角形…)
我们再写出它的对应方程组:
$$?\begin{array}{l}{a}_1+a_2=3\\ a_2+a_3=5\\ a_1+a_3=4\end{array}$$

求出它的对应式子
$a_1+a_2=3$
$a_1?a_2=?1$
$a_1?a_3=?2$
$a_1+a_3=4$

咦?..怎么每个$a$都有两个关系式？
实质上,是因为每个点都可以通过节点$1$,通过两条不同的路径到达节点$n$所造成的。
可以发现,每个$a$所拥有的两个关系式都可以相加直接求出唯一的$a_1$
即设$a_1+a_n=A$,$a_1?a_n=B$,那么$a_1=\frac{A+B}{2}$

那么环都能直接能确定$a_1$吗？
实际上，是不行的。

例如上图中的例子，$a_1$就有三个合法解$1,2,3$(具体求法可以参考第$1$部分的方程组)。
实质上是因为从节点$1$节点$n$的两条路径都是奇数,以至于两者的关系式不仅符号相同，连数值也相同。(使用$1$部分中的规律)
也就相当于一个式子了。

经过一系列的归纳与整理，我们发现:只要是奇环(即环的节点数有奇数个)，就能求出唯一的$a_1$,反之则不行(当然,在本题中,这并不是一个重要的结论)

这就是这道题的正解？
好像还漏了些什么…

3.排查&漏洞

没错…还有无解的情况
让我们返回样例$1$看看。
我们说过对于每一个$a$,都能确定唯一一个$a_1$。
但在无解的情况下它仍然成立吗?
肯定不一定。
因此，要判断无解，首先要确定通过其他$a$求出的每个$a_1$都相同。这是第一。

还有,前文说道环上的每个结点对于$a_1$都有两条路径。但如果有多个环，那就有多个关系式，那就有许多关系式相同的情况。如果当他们的关系式符号相同时(即$a_n+a_1=A$,$a_n+a_1=B$或者$a_n?a_1=A$,$a_n?a_1=B$),我们一定能得出$A=B$的结论,但如果$A?=B$,显然无解。这是第二。

第三是最简单的，即$1$部分中说提到的范围$max(B_1,B_2,...,B_{k_1},0)<a_1<min(A_1,A_2,...,A_{k_2})$无解。
设$A=min(A_1,A_2,...,A_{k_2})$,$B=max(B_1,B_2,...,B_{k_1},0)$,那么当$A?B?1\le 0$时，$a_1$无解。
这就是这道题的正解？

4.汇集&实现

没错，这就是这题的正解($QWQ$)
至于如何$BFS/DFS$,一般只有遍历顺序的问题，这里直接将记录关系式(不等式)的问题与遍历问题结合，即$vis[N][2]$
,这里$vis[N][0]$中存的是$a_1>B$中的$?B$(看后面代码的时候一定要注意这一点),目的是更简单直观，$vis[N][1]$中存的是$a_1<A$中的$A$;
然而还有一些细节需要提一下

1.图是双向的(蒟蒻没看清楚以至于调了2天的代码…)
2.$2$部分中，用奇环求$a_1$时最好放在$DFS/BFS$后单独求解
3.$2$部分中，用奇环求出的$a_1$一定要满足$1$部分中说提到的范围$max(B_1,B_2,...,B_{k_1},0)<a_1<min(A_1,A_2,...,A_{k_2})$,否则无解。
4.$1$部分中，一定要记得$a_1<A$,$a_1>B$,不是$a_1\le A$,$a_1\ge B$。

对了…$BFS/DFS$的时间复杂度是接近$O(n)$的。可以非常轻松地通过本题。
现在就是你们最喜欢的代码了233…
有点丑…

DFS版

#include<iostream>
#include<cstdio>
#include<cstring>
#include<climits>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
#define MAXN 100000
#define MAXM 100000
#define INF 1000000000000000
struct node
{
    int next,to;long long w;
}e[MAXM*2+5];
struct Qr
{
    int xr,dec;long long lim;
};
long long T;
int cnt,m,n;
int x,y,z,flag;
long long ri=INF,le=-INF;
long long vis[2][MAXN+5];
int b[MAXN+5];
void fpush(int u,int v,long long w)
{
    e[++cnt].next=b[u];e[cnt].w=w;e[cnt].to=v;b[u]=cnt;
}
int Ch(int x){
    if(x==-1)x=0;return x;}
void dfs(int xr,int dec,long long lim)
{
    if(flag)return ;for(int i=b[xr];i;i=e[i].next){
    int xnext=e[i].to;long long nlim=e[i].w-lim;int FD=Ch(dec);if(vis[FD][xnext]!=INF){
    if(vis[FD][xnext]!=nlim){
    flag=1;return ;}else continue;}vis[FD][xnext]=nlim;if(!FD)le=max(le,-vis[FD][xnext]);else ri=min(ri,vis[FD][xnext]);dfs(xnext,-dec,nlim);}
}
int main()
{
    fill(vis[0],vis[0]+MAXN+1,INF);fill(vis[1],vis[1]+MAXN+1,INF);scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){
    scanf("%d%d%d",&x,&y,&z);fpush(x,y,z);fpush(y,x,z);}dfs(1,1,0);if(flag){
    printf("0\n");return 0;}long long T=-1;for(int i=1;i<=n;i++)if(vis[0][i]!=INF&&vis[1][i]!=INF){
    long long NT=(vis[1][i]-vis[0][i])/2;if(NT<0){
    flag=1;break;}if(T==-1)T=NT;else if(T!=NT){
    flag=1;break;}}if(flag){
    printf("0\n");return 0;}if(T!=-1){
    if(T>le&&T<ri)printf("1\n");else printf("0\n");}else printf("%lld",max((long long)0,ri-le-1));
}

BFS版

#include<iostream>
#include<cstdio>
#include<cstring>
#include<climits>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
#define MAXN 100000
#define MAXM 100000
#define INF 1000000000000000
struct node
{
    int next,to;long long w;
}e[MAXM*2+5];
struct Qr
{
    int xr,dec;long long lim;
};
long long T;
int cnt,m,n;
int x,y,z,flag;
long long ri=INF,le=-INF;
long long vis[2][MAXN+5];
int b[MAXN+5];
void fpush(int u,int v,long long w)
{
    e[++cnt].next=b[u];e[cnt].w=w;e[cnt].to=v;b[u]=cnt;
}
int Ch(int x){
    if(x==-1)x=0;return x;}
int main()
{
    fill(vis[0],vis[0]+MAXN+1,INF);fill(vis[1],vis[1]+MAXN+1,INF);scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){
    scanf("%d%d%d",&x,&y,&z);fpush(x,y,z);fpush(y,x,z);}queue<Qr> Q;Q.push((Qr){
    1,1,0});while(!Q.empty()){
    Qr A=Q.front();Q.pop();int xr=A.xr,dec=A.dec;long long lim=A.lim;for(int i=b[xr];i;i=e[i].next){
    int xnext=e[i].to;long long nlim=e[i].w-lim;int FD=Ch(dec);if(vis[FD][xnext]!=INF){
    if(vis[FD][xnext]!=nlim){
    printf("0\n");return 0;}else continue;}vis[FD][xnext]=nlim;if(!FD)le=max(le,-vis[FD][xnext]);else ri=min(ri,vis[FD][xnext]);Q.push((Qr){
    xnext,-dec,nlim});}}long long T=-1;for(int i=1;i<=n;i++)if(vis[0][i]!=INF&&vis[1][i]!=INF){
    long long NT=(vis[1][i]-vis[0][i])/2;if(NT<0){
    flag=1;break;}if(T==-1)T=NT;else if(T!=NT){
    flag=1;break;}}if(flag){
    printf("0\n");}if(T!=-1){
    if(T>le&&T<ri)printf("1\n");else printf("0\n");}else printf("%lld",max((long long)0,ri-le-1));
}

END