利用矩阵快速幂转换的题目
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件不同的衣服,最后你获得价值最大
其实就是不断的换衣服,找到最大值,也就是矩阵快速幂找到最大值,这个思路其实就是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: 最短路径 ![分享至QQ空间](http://210.32.82.1/acmhome/forum/images/ico_qzone.gif)
题目地址: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
很早之前巨巨就为我解释过了,可是自己还是不太懂其中的意味,但是其实就是求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]); } }
相关文章
- 基于LM331的频率电压转换电路「建议收藏」
- MYSQL中日期与字符串间的相互转换
- JS隐式转换_隐式转换是什么
- char型和int型数据可以相互转换_c语言强制类型转换用法
- 如何快速地将WordPress文章内所有外部图片转换为本地链接?
- 【CSS3】CSS3 2D 转换 - rotate 旋转 ② ( 使用 rotate 旋转绘制三角形 )
- 一文带你玩转MySQL获取时间和格式转换各类操作方法详解
- 利用Linux时间戳快速转换时间(linux时间戳转换时间)
- Oracle数据转换成字符—实现快速而可靠的数据处理(oracle转换为字符)
- Oracle IP转换: 快速精准的解决方案(oracleip转换)
- 新闻速读 > Facebook 的 TransCoder AI 可在 Java、Python 和 C++ 之间转换代码
- 解读Oracle编码转换,优化数据库存储效率(oracle编码转换)
- Oracle小写转大写:快速实现大规模数据转换(oracle小写转大写)
- Linux下快速转换文件编码的实现方法(linux转换编码)
- Linux下快速视频格式转换指南(linux视频转换)
- 在 Linux 中快速转换时间:date 命令实战(linux时间转换命令)
- 将数据转换为 xml 格式:使用 MySQL 存储 xml 数据(mysql存xml)
- Linux 如何快速转换 IP 地址?(linux转换ip地址)
- Linux环境下轻松转换PDF文件(linux 转换pdf)
- Oracle数据强制转换:快速高效的表转换技巧分享(Oracle转表)
- MSSQL到PGSQL的快速转换,体验新的数据库系统(mssql转pgsql)
- MSSQL查询结果快速转换为表格(mssql 查结果生成表)
- 利用db2转oracle工具快速转换数据(db2转oracle工具)
- csv数据快速转换至MySQL数据库(.csv转mysql)
- 从临时表到Redis 实现数据更快速的转换(临时表变redis)
- phpIP转换整形(ip2long)的详解
- 探讨PHP函数ip2long转换IP时数值太大产生负数的解决方法
- php多层数组与对象的转换实例代码
- ORACLE毫秒与日期的相互转换示例