可以做旅游攻略的网站,微信手机网页版,官网seo是什么,汕头老城正题
题目链接:https://www.ybtoj.com.cn/problem/893 题目大意
给出一张nnn个点mmm条边的无向联通图#xff0c;每条边正反向各有A,B,CA,B,CA,B,C三种边权。 保证满足 Ax,y−Ay,x,Bx,yBy,x,Cx,y−Cy,xA_{x,y}-A_{y,x}\ ,\ B_{x,y}B_{y,x}\ ,\ C_{x,y}-C_{y,x}Ax,y−Ay,x…正题
题目链接:https://www.ybtoj.com.cn/problem/893 题目大意
给出一张nnn个点mmm条边的无向联通图每条边正反向各有A,B,CA,B,CA,B,C三种边权。 保证满足 Ax,y−Ay,x,Bx,yBy,x,Cx,y−Cy,xA_{x,y}-A_{y,x}\ ,\ B_{x,y}B_{y,x}\ ,\ C_{x,y}-C_{y,x}Ax,y−Ay,x , Bx,yBy,x , Cx,y−Cy,x ∑x−yCx,y0\sum_{x-y}C_{x,y}0x−y∑Cx,y0 且对于每个环[v1,v2...vn](v1vn)[v_1,v_2...v_n](v_1v_n)[v1,v2...vn](v1vn) ∑i1n−1Cvi,vi1×Bvi,vi1∑i1n−1Avi,vi1\sum_{i1}^{n-1}C_{v_i,v_{i1}}\times B_{v_i,v_{i1}}\sum_{i1}^{n-1}A_{v_i,v_{i1}}i1∑n−1Cvi,vi1×Bvi,vi1i1∑n−1Avi,vi1
现在给你A,BA,BA,B边权求CCC边权。
数据保证解唯一所有限制都在模PPP意义下
n∈[1,100],m∈[1,2000],P∈[1,1018]∪Prin\in[1,100],m\in[1,2000],P\in[1,10^{18}]\cup Prin∈[1,100],m∈[1,2000],P∈[1,1018]∪Pri 解题思路
最后一个环的限制很麻烦因为环很多。
先考虑原图的任意一颗生成树TTT上对于任意一条非树边(u,v)(u,v)(u,v)可以表示一个u−v−uu-v-uu−v−u的环。并且因为反过来走边权为负所以你可以通过用一些小环相互抵消出一个大环。
结论就是所有的环都可以被一些用非树边表示的环相互抵消表示。所以我们就可以将环的数量减少到O(m)O(m)O(m)级别了。
暴力消元O(m3)O(m^3)O(m3)显然无法通过本题我们还需要优化。
设Dx,yBx,y×Cx,y−Ax,yD_{x,y}B_{x,y}\times C_{x,y}-A_{x,y}Dx,yBx,y×Cx,y−Ax,y那么第一个条件就表示成了每个环DDD的和为000。
并且还能发现一个性质对于一个非树边表示的环(x,y)(x,y)(x,y) path(y,x)Dx,y0,path(x,y)−path(y,x),⇒Dx,ypath(x,y)path(y,x)D_{x,y}0,path(x,y)-path(y,x),\Rightarrow D_{x,y}path(x,y)path(y,x)Dx,y0,path(x,y)−path(y,x),⇒Dx,ypath(x,y) 其中path(x,y)path(x,y)path(x,y)表示树上路径x,yx,yx,y的DDD值和
所以可以证明从xxx走到yyy的所有路径权值相同
那么我们可以设fxpath(1,x)f_xpath(1,x)fxpath(1,x)那么Dx,yfy−fxD_{x,y}f_y-f_xDx,yfy−fx。
这样对于每个点就可以根据CCC的限制列出一个方程 ∑x−yfy−fxAx,yBx,y0\sum_{x-y}\frac{f_y-f_xA_{x,y}}{B_{x,y}}0x−y∑Bx,yfy−fxAx,y0
然后高斯消元即可时间复杂度O(n3)O(n^3)O(n3)
注意模数比较大要写龟速乘 code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N110;
struct node{ll x,y,a,b;
}e[N*20];
ll n,m,P,f[N];
ll mul(ll a,ll b){a%P;b%P;ll tmp(long double)a*b/P;long double ansa*b-tmp*P;if(ansP)ans-P;else if(ans0)ansP;return ans;
}
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansmul(ans,x);xmul(x,x);b1; }return ans;
}
namespace G{ll a[N][N],b[N];void solve(ll *f){for(ll i1;in;i){ll pi;for(ll ji;jn;j)if(a[j][i]){pj;break;}swap(a[i],a[p]);swap(b[i],b[p]);ll invpower(a[i][i],P-2);b[i]mul(b[i],inv);for(ll ji;jn;j)a[i][j]mul(a[i][j],inv);for(ll ji1;jn;j){ll rateP-a[j][i];for(ll ki;kn;k)a[j][k](a[j][k]mul(rate,a[i][k]))%P;b[j](b[j]mul(rate,b[i]))%P;}}for(ll in;i1;i--){for(ll ji1;jn;j)(b[i]P-mul(b[j],a[i][j]))%P;f[i]b[i];}return;}
}
signed main()
{freopen(graph.in,r,stdin);freopen(graph.out,w,stdout);scanf(%lld%lld%lld,n,m,P);for(ll i1;im;i)scanf(%lld%lld%lld%lld,e[i].x,e[i].y,e[i].a,e[i].b);for(ll i1;im;i){ll xe[i].x,ye[i].y,ae[i].a,be[i].b;bpower(b,P-2);(G::a[x][y]b)%P;(G::a[x][x]P-b)%P;(G::b[x]P-mul(a,b))%P;swap(x,y);aP-a;(G::a[x][y]b)%P;(G::a[x][x]P-b)%P;(G::b[x]P-mul(a,b))%P;}for(ll i1;in;i)G::a[1][i]0;G::a[1][1]1;G::b[1]0;G::solve(f);for(ll i1;im;i){ll xe[i].x,ye[i].y,ae[i].a,be[i].b;bpower(b,P-2);printf(%lld\n,mul((f[y]-f[x]aP)%P,b));}return 0;
}
