T-shirt
题目地址：https://nanti.jisuanke.com/t/28873
JSZKC is going to spend his vacation!
His vacation has NN days. Each day, he can choose a T-shirt to wear. Obviously, he doesn't want to wear a singer color T-shirt since others will consider he has worn one T-shirt all the time.
To avoid this problem, he has MM different T-shirt with different color. If he wears AA color T- shirt this day and BB color T-shirt the next day, then he will get the pleasure of f[A][B]f[A][B].(notice: He is able to wear one T-shirt in two continuous days but may get a low pleasure)
Please calculate the max pleasure he can get.
Input Format
The input file contains several test cases, each of them as described below.
-
The first line of the input contains two integers N,MN,M (2 \le N \le 100000, 1 \le M \le 100)(2≤N≤100000,1≤M≤100), giving the length of vacation and the T-shirts that JSZKC has.
-
The next follows MM lines with each line MMintegers. The j^{th}jth integer in the i^{th}ith line means f[i][j]f[i][j] (1\le f[i][j]\le 1000000)(1≤f[i][j]≤1000000).
There are no more than 1010 test cases.
Output Format
One line per case, an integer indicates the answer.
样例输入复制
3 2 0 1 1 0 4 3 1 2 3 1 2 3 1 2 3
样例输出复制
2 9
题目来源
The 2018 ACM-ICPC China JiangSu Provincial Programming Contest
这是我们邀请赛的一个题目，有n天，你可以换M件不同的衣服，最后你获得价值最大
其实就是不断的换衣服，找到最大值，也就是矩阵快速幂找到最大值1，这个思路其实就是floyd啊
我们需要注意的是第一天随便选一件，所以这一天不管就可以了，即求A(k-1)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=105; int G; struct MX { ll v[N][N]; void O() { memset(v,0,sizeof v); } void E() { memset(v,0,sizeof v); for(int i=0; i<G; i++)v[i][i]=1; } void P() { for(int i=0; i<G; i++) for(int j=0; j<G; j++)printf(j==G-1?"%d\n":"%d ",v[i][j]); } MX operator+(const MX &b) const { MX c; c.O(); for(int i=0; i<G; i++) for(int j=0; j<G; j++)c.v[i][j]=v[i][j]+b.v[i][j]; return c; } MX operator*(const MX &b)const { MX c; c.O(); for(int k=0; k<G; k++) for(int i=0; i<G; i++) for(int j=0; j<G; j++)c.v[i][j]=max(c.v[i][j],v[i][k]+b.v[k][j]); return c; } MX operator ^(int p)const { MX y,x; y.O(),memcpy(x.v,v,sizeof(v)); for(; p; x=x*x,p>>=1)if(p&1)y=y*x; return y; } } a,ans; int main() { int n,m; while(cin>>n>>m) { G=m; for(int i=0; i<G; i++) for(int j=0; j<G; j++)cin>>a.v[i][j]; ll ma=0; ans=a^(n-1); for(int i=0; i<G; i++) for(int j=0; j<G; j++)ma=max(ma,ans.v[i][j]); cout<<ma<<"\n"; } return 0; }
3444: 最短路径 
题目地址：http://210.32.82.1/acmhome/problemdetail.do?&method=showdetail&id=3444
Total Submit: 4 Accepted:2
Description
最短路径问题是图论中的经典问题。在实际的应用中，最短路径问题还有各种各样的变型，这里需要你解决的就是其中一个：
给定一个有向图G=(V,E)，E中的每条边都有可正可负的权值，表示距离。指定V中的两个顶u和w，请求出从u到w恰好含有k条边的最短路径。注意，路径可以重复经过同一条边。
Input
输入包含多组数据。
每组数据第一行包含三个整数， n, m, k，表示图中顶的数量，边的数量和最短路径的边数 (1≤n≤100, 0≤m≤n2, 1≤k≤109)
第二行包含两个整数u和w，表示起点和终点的编号。顶的编号在1到n之间。
其后m行，每行包含三个整数a, b, c，表示从编号为a的顶到编号为b的顶有一条权为c的边。输入保证没有重边，c的绝对值不超过1000。
输入以n=m=k=0结束，不要处理这组数据。
Output
对每组输入数据输出从u到w恰含k条边的最短路径长度，如果不存在这样的路径则输出”None”。注意答案可能会超过32位整型的范围。
Sample Input
1 1 2
1 1
1 1 1
2 2 999999999
1 2
1 2 1000
2 1 -100
2 2 1000000000
1 1
1 2 1000
2 1 -100
3 3 4
1 2
1 2 -1
2 3 1
3 1 1
3 3 5
1 2
1 2 -1
2 3 1
3 1 1
0 0 0
Sample Output
2
450000000100
450000000000
0
None
Source
USTC 2010
很早之前巨巨就为我解释过了，可是自己还是不太懂其中的意味，但是其实就是求A^k，所以你需要设置的矩阵是0 0，最后是INF
我偷懒，将初始矩阵也设置为a，那么A^(k-1)就可以做完
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=105; const ll INF=1e16; int G; struct MX { ll v[N][N]; void O() { for(int i=1; i<G; i++)for(int j=1; j<G; j++)v[i][j]=INF; } MX operator*(const MX &b)const { MX c; c.O(); for(int k=1; k<G; k++) for(int i=1; i<G; i++) for(int j=1; j<G; j++) if(v[i][k]!=INF&&b.v[k][j]!=INF)c.v[i][j]=min(c.v[i][j],v[i][k]+b.v[k][j]); return c; } MX operator^(int p)const { MX y,x; memcpy(x.v,v,sizeof v),memcpy(y.v,v,sizeof v); for(; p; x=x*x,p>>=1)if(p&1)y=y*x; return y; } } a,ans; int main() { int n,m,k,s,t; while(scanf("%d%d%d",&n,&m,&k),n+m+k) { G=n+1; scanf("%d%d",&s,&t); a.O(); for(int i=0,u,v,w;i<m;i++) scanf("%d%d%d",&u,&v,&w),a.v[u][v]=w; ans=a^(k-1); if(ans.v[s][t]==INF)printf("None\n"); else printf("%I64d\n",ans.v[s][t]); } }