题目大意

n个点n条边的联通无向图，每个点i有一个[0,p)的数xi，p是个质数。 每条边(u,v)都有一条方程形如 a∗xu+b∗xv≡c(mod p) 保证x有解且有唯一解，求出x。

解方程

假定一个位置的值是x，然后从这个位置bfs通过边上的方程用x表示出其余每个点的值。 因为一定有环所以可以在某条边上解方程得到x。

#include<cstdio> #include<algorithm> #define fo(i,a,b) for(i=a;i<=b;i++) using namespace std; typedef long long ll; const int maxn=100000+10; int h[maxn],go[maxn*2],nxt[maxn*2],a[maxn*2],b[maxn*2],c[maxn*2]; int kk[maxn],bb[maxn],dl[maxn],d[maxn],fa[maxn]; int i,j,k,l,r,t,n,m,p,head,tail,xx,tot,now; bool czy; int qsm(int x,int y){ if (!y) return 1; int t=qsm(x,y/2); t=(ll)t*t%p; if (y%2) t=(ll)t*x%p; return t; } void add(int x,int y,int aa,int bb,int cc){ go[++tot]=y; a[tot]=aa; b[tot]=bb; c[tot]=cc; nxt[tot]=h[x]; h[x]=tot; } int main(){ //freopen("C.in","r",stdin); scanf("%d%d",&n,&p); fo(i,1,n){ scanf("%d%d%d%d%d",&j,&k,&l,&r,&t); add(j,k,l,r,t);add(k,j,r,l,t); } head=0;tail=1; dl[1]=1; d[1]=1; kk[1]=1;bb[1]=0; while (head<tail){ now=dl[++head]; t=h[now]; while (t){ if (d[go[t]]==0){ d[go[t]]=1; kk[go[t]]=(p-(ll)a[t]*qsm(b[t],p-2)%p*kk[now]%p)%p; bb[go[t]]=(ll)(c[t]-(ll)a[t]*bb[now]%p)%p*qsm(b[t],p-2)%p; dl[++tail]=go[t]; fa[go[t]]=now; } else{ k=((ll)kk[now]*a[t]%p+(ll)kk[go[t]]*b[t]%p)%p; if (k){ r=((ll)bb[now]*a[t]%p+(ll)bb[go[t]]*b[t]%p)%p; xx=(ll)(c[t]-r)%p*qsm(k,p-2)%p; } } t=nxt[t]; } } fo(i,1,n){ t=((ll)kk[i]*xx%p+bb[i])%p; (t+=p)%=p; printf("%d\n",t); } }