題目鏈接: (bzoj) https://www.lydsy.com/JudgeOnline/problem.php?id=4386
(luogu) https://www.luogu.org/problemnew/show/P3597

為啥這種題我都不會了啊
題解: 首先如果邊權(quán)全都為\(1\), 那么就新建一個計數(shù)器，每個點連計數(shù)器，計數(shù)器連個自環(huán)。然后鄰接矩陣快速冪倍增即可
如果邊權(quán)有\(2\)和\(3\), 就分別新建一個節(jié)點連向出點
細(xì)節(jié)不少，特別是判斷是否大于\(k\)的時候不能爆long long(據(jù)說這題數(shù)據(jù)水，所以我不敢保證下面的代碼不會被卡)

代碼

#include<cstdio> #include<cstdlib> #include<cstring> #include<cassert> #include<iostream> #define llong long long using namespace std;inline int read() {int x=0; bool f=1; char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=0;for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');if(f) return x;return -x; }const int N = 121; llong p; struct Matrix {llong a[N+3][N+3]; int n;Matrix() {}Matrix(int _n) {n = _n; for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) a[i][j] = 0ll;}void init(int _n) {n = _n; for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) a[i][j] = 0ll;}void unitize(int _n) {n = _n; a[0][0] = 0ll; for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) a[i][j] = i==j?1ll:0ll;}void output() {if(a[0][0]==-1) puts("gg"); for(int i=1; i<=n; i++) {for(int j=1; j<=n; j++) printf("%d ",a[i][j]); puts("");}}Matrix operator *(const Matrix &arg) const{Matrix ret(n);for(int i=1; i<=n; i++){for(int j=1; j<=n; j++){for(int k=1; k<=n; k++){if(k==n){if(arg.a[j][k]>0 && (a[i][j]>=p/arg.a[j][k]+1 || ret.a[i][k]>=p-a[i][j]*arg.a[j][k])){ret.a[0][0] = -1;return ret;}}ret.a[i][k] = ret.a[i][k]+a[i][j]*arg.a[j][k];}}}llong sum = 0ll;for(int i=1; i<=n/3; i++){if(sum>=p-ret.a[i][n]) {ret.a[0][0] = -1; return ret;}sum += ret.a[i][n];}return ret;} } g,pw[65],tmp; int n,m;llong solve() {pw[0] = g; int i = 0;for(i=1; i<=61; i++){pw[i] = pw[i-1]*pw[i-1];if(pw[i].a[0][0]==-1){break;}}if(i==62) {return -1;}llong ret = 0ll; g.unitize(n+n+n+1);for(i--; i>=0; i--){tmp = g*pw[i];if(tmp.a[0][0]!=-1){ret|=(1ll<<i);g = tmp;}}return ret; }int main() {scanf("%d%d%lld",&n,&m,&p); p+=n;g.init(n+n+n+1);for(int i=1; i<=m; i++){int x,y,w; scanf("%d%d%d",&x,&y,&w);if(w==1) {g.a[x][y]++;}else if(w==2) {g.a[x+n][y]++;}else if(w==3) {g.a[x+n+n][y]++;}}for(int i=1; i<=n; i++){g.a[i][i+n]++;g.a[i+n][i+n+n]++;g.a[i][n+n+n+1]++;}g.a[n+n+n+1][n+n+n+1]++;llong ans = solve();printf("%lld\n",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的BZOJ 4386 Luogu P3597 [POI2015]Wycieczki (矩阵乘法)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。