题面
Time limit : 2sec / Memory limit : 1024MB
Score : 600 points
Problem Statement-题目描述
Kenkoooo found a simple connected graph. The vertices are numbered 1" role="presentation">11 through n" role="presentation">nn. The i" role="presentation">ii-th edge connects Vertex ui" role="presentation">uiui and vi" role="presentation">vivi, and has a fixed integer si" role="presentation">sisi.
Kenkoooo is trying to write a positive integer in each vertex so that the following condition is satisfied:
For every edge i" role="presentation">ii, the sum of the positive integers written in Vertex ui" role="presentation">uiui and vi" role="presentation">vivi is equal to si" role="presentation">sisi.
Find the number of such ways to write positive integers in the vertices.
Constraints-数据范围
2≤n≤105" role="presentation" style="position: relative;">2≤n≤1052≤n≤105
1≤m≤105" role="presentation" style="position: relative;">1≤m≤1051≤m≤105
1≤ui<vi≤n" role="presentation" style="position: relative;">1≤ui<vi≤n1≤ui<vi≤n
2≤si≤109" role="presentation" style="position: relative;">2≤si≤1092≤si≤109
If i≠j" role="presentation" style="position: relative;">i≠ji≠j, then ui≠uj" role="presentation" style="position: relative;">ui≠ujui≠uj or vi≠vj." role="presentation" style="position: relative;">vi≠vj.vi≠vj.
The graph is connected.
All values in input are integers.
题目大意
给你一个无向图G=(V,E)" role="presentation" style="position: relative;">G=(V,E)G=(V,E),定义任意一条边e=(i,j)" role="presentation" style="position: relative;">e=(i,j)e=(i,j) (i≠j,i∈V,j∈V)" role="presentation" style="position: relative;">(i≠j,i∈V,j∈V)(i≠j,i∈V,j∈V)的权值为wi,j" role="presentation" style="position: relative;">wi,jwi,j,任意一个点ci(c∈V)" role="presentation" style="position: relative;">ci(c∈V)ci(c∈V)的权值为wi" role="presentation" style="position: relative;">wiwi,且wi" role="presentation" style="position: relative;">wiwi为正整数,现在给出所有边e" role="presentation" style="position: relative;">ee和边的权值wi,j" role="presentation" style="position: relative;">wi,jwi,j,求所有边与点都满足wi,j=wi+wj" role="presentation" style="position: relative;">wi,j=wi+wjwi,j=wi+wj时,1号结点有多少种不同的取值。
2≤n≤105" role="presentation" style="position: relative;">2≤n≤1052≤n≤105
1≤m≤105" role="presentation" style="position: relative;">1≤m≤1051≤m≤105
1≤ui<vi≤n" role="presentation" style="position: relative;">1≤ui<vi≤n1≤ui<vi≤n
2≤si≤109" role="presentation" style="position: relative;">2≤si≤1092≤si≤109
题解
1.确定&方向
学过差分约束的同学可能会感觉这题与差分约束十分类似,是的。差分约束可以维护ai−aj≤X" role="presentation" style="position: relative;">ai−aj≤Xai−aj≤X的情况,同时,ai−aj=X" role="presentation" style="position: relative;">ai−aj=Xai−aj=X也可以转成ai−aj≤X" role="presentation" style="position: relative;">ai−aj≤Xai−aj≤X进行差分约束。但题目的要求是ai+aj=X" role="presentation" style="position: relative;">ai+aj=Xai+aj=X,至少在蒟蒻的知识范围内,是无法转化(或者很难转化)的。
这时候我们就又需要从暴力开始思考了。首先考虑枚举的变量应该是什么。
我们以样例2作为例子
4 3
1 2 6
2 3 7
3 4 5
显然我们可以将这些条件化成方程组
我们很快可以发现只要我们知道其中的任意一个值,我们就可以求出所有的a" role="presentation" style="position: relative;">aa。
我们不妨直接枚举a1" role="presentation" style="position: relative;">a1a1,判断它是否成立即可。
然而这样做一定是超时的,因此我们需要一个更好的方法来节省时间。
对方程比较敏感的同学很快会忍不住将1,2" role="presentation" style="position: relative;">1,21,2式相减得出a1−a3=−1" role="presentation" style="position: relative;">a1−a3=−1a1−a3=−1,再将其与3" role="presentation" style="position: relative;">33式相加得出a1+a4=4" role="presentation" style="position: relative;">a1+a4=4a1+a4=4。
这样一来,我们就求出a1" role="presentation" style="position: relative;">a1a1与其他a" role="presentation" style="position: relative;">aa的关系。
但是这有何用呢。
再看看题目,题目要求ai>0" role="presentation" style="position: relative;">ai>0ai>0。显然我们需要往求范围的方向想问题。
因为a2=6−a1>0" role="presentation" style="position: relative;">a2=6−a1>0a2=6−a1>0,a3=a1+1>0" role="presentation" style="position: relative;">a3=a1+1>0a3=a1+1>0,a4=4−a1>0" role="presentation" style="position: relative;">a4=4−a1>0a4=4−a1>0。
我们就可以得到a1<6" role="presentation" style="position: relative;">a1<6a1<6,a1>−1" role="presentation" style="position: relative;">a1>−1a1>−1,a1<4" role="presentation" style="position: relative;">a1<4a1<4,和a1>0" role="presentation" style="position: relative;">a1>0a1>0结合得0<a1<4" role="presentation" style="position: relative;">0<a1<40<a1<4即a1" role="presentation" style="position: relative;">a1a1有3" role="presentation" style="position: relative;">33个取值。没错,这就是正确答案了。
根据上面的操作我们可以发现几个有用的规律
1.当n≡0(mod2)" role="presentation" style="position: relative;">n≡0(mod2)n≡0(mod2)(即n%2=0)时,总有a1+an=A" role="presentation" style="position: relative;">a1+an=Aa1+an=A,换成不等式即a1<A" role="presentation" style="position: relative;">a1<Aa1<A。
2.当n≡1(mod2)" role="presentation" style="position: relative;">n≡1(mod2)n≡1(mod2)(即n%2=1)时,总有a1−an=B" role="presentation" style="position: relative;">a1−an=Ba1−an=B,换成不等式即a1>B" role="presentation" style="position: relative;">a1>Ba1>B。
显然,答案a1" role="presentation" style="position: relative;">a1a1的范围即为max(B1,B2,...,Bk1,0)<a1<min(A1,A2,...,Ak2)" role="presentation" style="position: relative;">max(B1,B2,...,Bk1,0)<a1<min(A1,A2,...,Ak2)max(B1,B2,...,Bk1,0)<a1<min(A1,A2,...,Ak2)
直接用DFS/BFS" role="presentation" style="position: relative;">DFS/BFSDFS/BFS遍历整张图很容易求出范围与a1" role="presentation" style="position: relative;">a1a1的合法个数。
难道这就是这道题的正解?
2.尝试&完善
作为这场比赛的最后一题,绝对不可能这么简单。
上面的样例显然遗漏了我们的老朋友(233)——环。
这个关系在环上也成立吗?
让我们来看看第一组样例吧。
3 3
1 2 3
2 3 5
1 3 4
(莫名画成直角三角形…)
我们再写出它的对应方程组:
求出它的对应式子
a1+a2=3" role="presentation" style="position: relative;">a1+a2=3a1+a2=3
a1−a2=−1" role="presentation" style="position: relative;">a1−a2=−1a1−a2=−1
a1−a3=−2" role="presentation" style="position: relative;">a1−a3=−2a1−a3=−2
a1+a3=4" role="presentation" style="position: relative;">a1+a3=4a1+a3=4
咦?…怎么每个a" role="presentation" style="position: relative;">aa都有两个关系式?
实质上,是因为每个点都可以通过节点1" role="presentation" style="position: relative;">11,通过两条不同的路径到达节点n" role="presentation" style="position: relative;">nn所造成的。
可以发现,每个a" role="presentation" style="position: relative;">aa所拥有的两个关系式都可以相加直接求出唯一的a1" role="presentation" style="position: relative;">a1a1
即设a1+an=A" role="presentation" style="position: relative;">a1+an=Aa1+an=A,a1−an=B" role="presentation" style="position: relative;">a1−an=Ba1−an=B,那么a1=A+B2" role="presentation" style="position: relative;">a1=A+B2a1=A+B2
那么环都能直接能确定a1" role="presentation" style="position: relative;">a1a1吗?
实际上,是不行的。
例如上图中的例子,a1" role="presentation" style="position: relative;">a1a1就有三个合法解1,2,3" role="presentation" style="position: relative;">1,2,31,2,3(具体求法可以参考第1" role="presentation" style="position: relative;">11部分的方程组)。
实质上是因为从节点1" role="presentation" style="position: relative;">11节点n" role="presentation" style="position: relative;">nn的两条路径都是奇数,以至于两者的关系式不仅符号相同,连数值也相同。(使用1" role="presentation" style="position: relative;">11部分中的规律)
也就相当于一个式子了。
经过一系列的归纳与整理,我们发现:只要是奇环(即环的节点数有奇数个),就能求出唯一的a1" role="presentation" style="position: relative;">a1a1,反之则不行(当然,在本题中,这并不是一个重要的结论)
这就是这道题的正解?
好像还漏了些什么…
3.排查&漏洞
没错…还有无解的情况
让我们返回样例1" role="presentation" style="position: relative;">11看看。
我们说过对于每一个a" role="presentation" style="position: relative;">aa,都能确定唯一一个a1" role="presentation" style="position: relative;">a1a1。
但在无解的情况下它仍然成立吗?
肯定不一定。
因此,要判断无解,首先要确定通过其他a" role="presentation" style="position: relative;">aa求出的每个a1" role="presentation" style="position: relative;">a1a1都相同。这是第一。
还有,前文说道环上的每个结点对于a1" role="presentation" style="position: relative;">a1a1都有两条路径。但如果有多个环,那就有多个关系式,那就有许多关系式相同的情况。如果当他们的关系式符号相同时(即an+a1=A" role="presentation" style="position: relative;">an+a1=Aan+a1=A,an+a1=B" role="presentation" style="position: relative;">an+a1=Ban+a1=B或者an−a1=A" role="presentation" style="position: relative;">an−a1=Aan−a1=A,an−a1=B" role="presentation" style="position: relative;">an−a1=Ban−a1=B),我们一定能得出A=B" role="presentation" style="position: relative;">A=BA=B的结论,但如果A≠B" role="presentation" style="position: relative;">A≠BA≠B,显然无解。这是第二。
第三是最简单的,即1" role="presentation" style="position: relative;">11部分中说提到的范围max(B1,B2,...,Bk1,0)<a1<min(A1,A2,...,Ak2)" role="presentation" style="position: relative;">max(B1,B2,...,Bk1,0)<a1<min(A1,A2,...,Ak2)max(B1,B2,...,Bk1,0)<a1<min(A1,A2,...,Ak2)无解。
设A=min(A1,A2,...,Ak2)" role="presentation" style="position: relative;">A=min(A1,A2,...,Ak2)A=min(A1,A2,...,Ak2),B=max(B1,B2,...,Bk1,0)" role="presentation" style="position: relative;">B=max(B1,B2,...,Bk1,0)B=max(B1,B2,...,Bk1,0),那么当A−B−1≤0" role="presentation" style="position: relative;">A−B−1≤0A−B−1≤0时,a1" role="presentation" style="position: relative;">a1a1无解。
这就是这道题的正解?
4.汇集&实现
没错,这就是这题的正解(QWQ" role="presentation" style="position: relative;">QWQQWQ)
至于如何BFS/DFS" role="presentation" style="position: relative;">BFS/DFSBFS/DFS,一般只有遍历顺序的问题,这里直接将记录关系式(不等式)的问题与遍历问题结合,即vis[N][2]" role="presentation" style="position: relative;">vis[N][2]vis[N][2]
,这里vis[N][0]" role="presentation" style="position: relative;">vis[N][0]vis[N][0]中存的是a1>B" role="presentation" style="position: relative;">a1>Ba1>B中的−B" role="presentation" style="position: relative;">−B−B(看后面代码的时候一定要注意这一点),目的是更简单直观,vis[N][1]" role="presentation" style="position: relative;">vis[N][1]vis[N][1]中存的是a1<A" role="presentation" style="position: relative;">a1<Aa1<A中的A" role="presentation" style="position: relative;">AA;
然而还有一些细节需要提一下
1.图是双向的(蒟蒻没看清楚以至于调了2天的代码..)
2.2" role="presentation" style="position: relative;">22部分中,用奇环求a1" role="presentation" style="position: relative;">a1a1时最好放在DFS/BFS" role="presentation" style="position: relative;">DFS/BFSDFS/BFS后单独求解
3.2" role="presentation" style="position: relative;">22部分中,用奇环求出的a1" role="presentation" style="position: relative;">a1a1一定要满足1" role="presentation" style="position: relative;">11部分中说提到的范围max(B1,B2,...,Bk1,0)<a1<min(A1,A2,...,Ak2)" role="presentation" style="position: relative;">max(B1,B2,...,Bk1,0)<a1<min(A1,A2,...,Ak2)max(B1,B2,...,Bk1,0)<a1<min(A1,A2,...,Ak2),否则无解。
4.1" role="presentation" style="position: relative;">11部分中,一定要记得a1<A" role="presentation" style="position: relative;">a1<Aa1<A,a1>B" role="presentation" style="position: relative;">a1>Ba1>B,不是a1≤A" role="presentation" style="position: relative;">a1≤Aa1≤A,a1≥B" role="presentation" style="position: relative;">a1≥Ba1≥B。
对了….BFS/DFS" role="presentation" style="position: relative;">BFS/DFSBFS/DFS的时间复杂度是接近O(n)" role="presentation" style="position: relative;">O(n)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];
long long T;
int cnt,m,n;
int x,y,z,flag;
long long ri=INF,le=1;
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 lim,int dec)
{
for(int i=b[xr];i;i=e[i].next)
{
int xnext=e[i].to;
int FD=Ch(dec);
if(vis[FD][xnext]!=INF)
{
if(vis[FD][xnext]!=lim+e[i].w*dec){flag=1;return ;}
else continue;
}
vis[FD][xnext]=lim+e[i].w*dec;
if(!FD)le=max(le,-vis[FD][xnext]);
else ri=min(ri,vis[FD][xnext]);
dfs(xnext,lim+e[i].w*dec,-dec);
}
}
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,0,1);
long long T=0;
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<=le&&NT>=ri){flag=1;break;}
if(NT<=0){flag=1;break;}
if(T==0)T=NT;
else if(T!=NT){flag=1;break;}
}
if(flag){printf("0\n");;}
if(T)printf("1\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));
}