摘要: 求所谓的 optimal path:对某个顶点,只能沿着它所有出边中weight最小的那些路走;从起点到终点的总weight最小;如果有weight相同的,取总length最短的.可能有负环,自环,平行边.
先将不符合要求的边删掉.接着,关键在于如何判断有效负环,即该负环处在起点到终点的路上.实际上,只用保留原图中从起点能到达,并且能到达终点的顶点.如果用标准bellman-ford,需要2次D...
阅读全文
命题：一棵有n(n>=2)个叶子结点的树，至少须添加ceil(n/2)条边，就能转变为一个没有桥的图。或者说，使得图中每条边，都至少在一个环上。
证明：
这里只证明n为偶数的情况。n为奇数的证明类似。证明采用了构造解、极端法、归纳法的方法技巧。
先证明添加n/2条边一定可以达成目标。
n=2时，显然只需将这两个叶子间连一条边即可。命题成立。
设n=2k(k>=1)时命题成立，即S[2k]=k。下面将推出n=2(k+1)时命题亦成立。
n=2k+2时，选取树中最长的迹，设其端点为a,b；并设离a最近的度>=3的点为a',同理设b'。
（关于a'和b'的存在性问题：由于a和b的度都为1,因此树中其它的树枝必然从迹<a,b>之间的某些点引出。否则整棵树就是迹<a,b>，n=2<2k+2，不可能。）
在a,b间添一条边，则迹<a,b>上的所有边都已不再是桥。这时，将刚才添加的边，以及aa'之间，bb'之间的边都删去，得到一棵新的树。因为删去的那些边都已经符合条件了，所以在之后的构造中不需要考虑它们。由于之前a'和b'的度>=3，所以删除操作不会使他们变成叶子。因此新的树必然比原树少了两个叶子a,b，共有2k个叶子。由归纳知需要再加k条边。因此对n=2k+2的树，一共要添加k+1条边。
因此证得n/2可取。
再证明n/2是最小的解。
显然，只有一个叶子结点被新加的边覆盖到，才有可能使与它相接的那条边进入一个环中。而一次加边至多覆盖2个叶子。因此n个叶子至少要加n/2条边。
证毕。
http://acm.hdu.edu.cn/showproblem.php?pid=1005A number sequence is defined as follows:
f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
Given A, B, and n, you are to calculate the value of f(n).
1 <= A, B <= 1000, 1 <= n <= 100,000,000
解:
f(n) = (A * f(n - 1) + B * f(n - 2)) %7
= (A * f(n - 1) %7 + B * f(n - 2) %7) %7
所以对于给定的A和B,可以先打表,找出数列的循环部分. 鸽巢原理知,状态总数不会超过7*7
注意循环节不一定从f(3)开始...
1
#include <iostream>
2using namespace std;
3
4int a,b,n,x,y,l,h,m[7][7],q[300];
5
int main()
{
6
while(scanf("%d%d%d",&a,&b,&n)!=EOF && (a||b||n)){
7
memset(m, 0, sizeof(m));
8 q[1] = q[2] = 1;
9 x = y = 1; l=3;
10 while(m[x][y]==0){ //该状态还未经历过,则扩展
11 q[l] = (a*x+b*y)%7;
12 m[x][y] = l;
13 y = x;
14 x = q[l++];
15
}
16 //此时,q[1h-1]为前面的非循环部分
17 //q[hl-1]为循环节
18 h = m[x][y]; //循环节的起始位置
19 if(n<h) printf("%d\n",q[n]);
20 else printf("%d\n",q[((n-h)%(l-h))+h]);
21 }
22 return 0;
23
}
http://acm.cist.bnu.edu.cn/contest/problem_show.php?pid=1069给一些物品,虚拟币价格v[i]=2^(ki-1),实际价值w[i].现给S个虚拟币.要求把这些虚拟币恰好花完,并且购得物品的实际价值总和最大.
显然,可行的购买方案必能将所购物品分成若干组,其中每组的总价格为2^(pi-1),其中pi为S的二进制表示为1的所有位.
因此可以按位贪心,从S的最低位开始.设当前处理第k位:
1.选取剩余物品价格为2^(k-1)中价值最大的那个,如果没有价格为2^(k-1)的物品,则表示任务无法达成.
2.将其它价格为2^(k-1)的物品,按价值从大到小排序,相邻两个合并成价格为2^k的物品,累积到下一阶段.
这里挖掘出的贪心性质为: 一个数第k位的1,只能由不高于第k位的1合成得到.
http://acm.pku.edu.cn/JudgeOnline/problem?id=1276题目大意是:
给定N种面值分别为d[k]的钞票,数量分别为n[k]张.再给一个整数cash.
求,用这些钞票能表示出的不大于cash的最大值是多少.
数据范围N<=1000, n[k]<=1000, cash<=100000
最简单的DP思路是大背包.把每一张钞票看成一件物品,把cash看成背包容量.
这样的复杂度是O(sigma(n[k])*cash),上限是10^11,显然难以应付1000ms的时限.
此处便需利用一个整数的性质来压缩钞票数:
易知,1,2,4,...,2^(k-1)这些数的线性组合,可以表示出任意小于2^k的正整数.
所以如果n[i]=2^k-1,那么实际上钞票k,就可以转化为分别用系数(1,2,4,...,2^k-1)去乘d[k]而得到的钞票各一张.
如果n[i]!=2^k-1,只需取系数1,2,4,..,2^(k-1),n[i]-(2^k-1),其中k是使2^k-1<=n[i]的最大整数.
代码如下:
1 #include <iostream>
2 #include <algorithm>
3 using namespace std;
4 int dp[100010],mark;
5 int sn,cash;
6 struct BILL{
7 int n,d;
8 }b[1010];
9 int ans;
10
11 void go_dp(){
12 int i,k,upb,r,s;
13 dp[0]=mark;
14 ans=0;
15 for(k=0; k<sn; k++){
16 r=1; //系数:2的幂次
17 while(b[k].n>0){
18 if((r<<1)-1>b[k].n){
19 r=b[k].n-(r-1);
20 b[k].n=0;
21 }
22 s=r*b[k].d; //新钞票的面值
23 upb=min(ans+s,cash);
24 for(i=upb; i>=s; i--){
25 if(dp[i-s]==mark){
26 dp[i]=mark;
27 if(ans<i) ans=i;
28 }
29 }
30 r<<=1;
31 if(ans==cash) return;
32 }
33 }
34 }
35
36 int main(){
37 int i,j,k;
38 mark=0;
39 while(scanf("%d%d",&cash,&sn)!=EOF){
40 ans=0; mark++;
41 for(i=0;i<sn;i++){
42 scanf("%d%d",&b[i].n,&b[i].d);
43 ans+=b[i].n*b[i].d;
44 }
45 if(ans>cash)
46 go_dp();
47
48 printf("%d\n",ans);
49 }
50 return 0;
51 }
52
另,在网上搜得另一种思路,开bool数组记录每个总额是否能达到,开个2维数组记录达到相应总额每种钞票使用数
个人以为,这种方法不能保证总得到最优解.考察如下的例子:
cash=3*4*5=60
钞票(面值*张数):3*19,4*14,5*11
假设55的方案恰好是5*11,56的方案恰好是4*14,57的方案恰好是3*19,那么在考虑60时就找不到解了.实际上60是可以达到的.
最近做了两道floyd变种的题目,又加深了对floyd原理的理解.
第2题: tju 3214 Find the Path
http://acm.tju.edu.cn/toj/showp3214.html
题目大意是给一个无向图,每个结点有个点权c[p]
对于查询的点对i,j和权k,求在中间节点(不包含端点i,j)权值不大于k的限制下,i,j间最短路径.
由于查询次数多,因此一次查询复杂度需要在O(logn)以内.考虑计算出所有点对在所有限制条件下的最短路,O(1)查询.
限制条件不作用于端点i,j,正好可以用floyd解决.因为floyd正是不断向中间点集中加入点.只要限制一下这些被加入点的条件,就可以解决这题了.
初步归纳,对于查询i,j,k,应该输出将所有c[p]<=k的点加入后的floyd[i,j]
对于限制k,点集的情况是:加了权最小的m个(0<=m<=N),这些点的权都不超过k
因此将点按权值升序排列.dist[k][i][j]表示:前k个点被加入后,i,j间的最短路.
代码如下:
1#include <iostream>
2using namespace std;
3int T,N,M,Q,pc[210];
4int C[210],dist[210][210][210];
5bool mycmp(int a, int b){
6 return (C[a]<C[b]);
7}
8int main(){
9 int i,j,k,p,a,b,c;
10 scanf("%d",&T);
11 while(T--){
12 memset(dist,0xff,sizeof(dist));
13 scanf("%d%d",&N,&M);
14 C[pc[0]=0]=-1;
15 for(i=1;i<=N;i++){
16 scanf("%d",&C[i]);
17 pc[i]=i;
18 }
19 sort(pc,pc+N+1,mycmp);
20 for(i=1; i<=M; i++){
21 scanf("%d%d%d",&a,&b,&c);
22 dist[0][a+1][b+1]=c;
23 dist[0][b+1][a+1]=c;
24 }
25 //floyd
26 for(k=1; k<=N; k++){
27 p=pc[k];
28 for(i=1; i<=N; i++){
29 for(j=1; j<=N; j++){
30 if(dist[k][i][j]<0)
31 dist[k][i][j]=dist[k-1][i][j];
32 else if(dist[k-1][i][j]>=0)
33 dist[k][i][j]=min(dist[k][i][j],dist[k-1][i][j]);
34
35 if(i!=j && dist[k-1][i][p]>=0 && dist[k-1][p][j]>=0){
36 if(dist[k][i][j]<0)
37 dist[k][i][j]=dist[k-1][i][p]+dist[k-1][p][j];
38 else
39 dist[k][i][j]=min(dist[k][i][j], dist[k-1][i][p]+dist[k-1][p][j]);
40 }
41 //printf("%d,%d,%d(%d) ",k,i,j,dist[k][i][j]);
42 }
43 }
44 }
45 //query
46 scanf("%d",&Q);
47 while(Q--){
48 scanf("%d%d%d",&a,&b,&c);
49 //顺序查找
50 for(i=0; i<=N && C[pc[i]]<=c; i++);
51 printf("%d\n",dist[i-1][a+1][b+1]);
52 }
53 printf("\n");
54 }
55 return 0;
56}
57
最近做了两道floyd变种的题目,又加深了对floyd原理的理解.
第1题: bupt 1460 游览路线
http://acm.cs.bupt.cn/onlinejudge/showproblem.php?problem_id=1460大意是给定一个无向图,找出一个环,使得环的长度最短,并且这个环上至少有3个顶点.
一种O(mn^2)的做法是枚举每条边<u,v>,用dijkstra求由原图删去这条边后的新图中u,v间最短路径dist[u,v],该环长度即为map[u,v]+dist[u,v].输出环长度值最小的那个.
仔细分析知道,这题实际上是要求每对点u,v间不包含边<u,v>的最短路径.想到floyd正是计算所有点对最短路径的.但是这里不能包含边<u,v>的条件就是变化所在.
floyd的原理是依次往"中间点集"中加入点k,再更新任意点对dist[i,j].
此题中,如果直接枚举map[i,k]+map[k,j]+floyd[i,j](floyd[i,j]为使用经典算法得到的两点间最短路),有可能出现一个点经过两次的情况.比如由边集{(1,2),(1,3),(1,4)}构成的图,依题意是无解,但是用错误的枚举方法却有解.原因是没有排除(1->2),(2->1->3),(3->1)的情况.此时可以看出,以点k为原点枚举i,j时的floyd[i,j]应该是保证不经过k的,也就是枚举操作应该在往"中间点集"中加入k之前!
这样可以得出算法的大致轮廓:在加入点k前更新dist[i,j]
但是问题是,此时的中间点只有1..k-1,那后面的点k+1..n会不会漏处理呢?
本质上,这题求的是环的长度,而不是路径长度.因此,假如存在一个更短的环,它路径上有k之后的点p1,p2,...,pm,设其中最后处理的那个点是pl.那么这个环一定会在向中间点集中加入pl的那次循环里枚举到.
因此不存在漏解问题.
代码如下:
1 #include <iostream>
2 using namespace std;
3 int N,M,ans;
4 //w是原图矩阵,d是floyd最短路矩阵
5 int w[110][110],d[110][110];
6 int main(){
7 int i,j,k,a,b,c;
8 while(scanf("%d%d",&N,&M)!=EOF){
9 for(i=1;i<=N;i++)
10 for(j=1;j<=N;j++)
11 w[i][j]=d[i][j]=0;
12 for(i=1;i<=M;i++){
13 scanf("%d%d%d",&a,&b,&c);
14 if(!w[a][b]||c<w[a][b]){
15 w[a][b]=w[b][a]=c;
16 d[a][b]=d[b][a]=c;
17 }
18 }
19 ans=0x7fffffff;
20 for(k=1;k<=N;k++){
21 //先枚举map[i,k]+map[k,j]+floyd[i,j]
22 for(i=1;i<k;i++)
23 for(j=i+1;j<k;j++)
24 if(w[i][k]&&w[k][j]&&d[i][j])
25 ans=min(ans,d[i][j]+w[i][k]+w[k][j]);
26 //再向中间点集中加入k并更新floyd矩阵
27 for(i=1;i<=N;i++){
28 if(!d[i][k])continue;
29 for(j=1;j<=N;j++){
30 if(!d[k][j]||i==j)continue;
31 if(!d[i][j]||d[i][j]>d[i][k]+d[k][j])
32 d[i][j]=d[i][k]+d[k][j];
33 }
34 }
35 }
36 if(ans<0x7fffffff)
37 printf("%d\n",ans);
38 else
39 puts("No solution.");
40 }
41 return 0;
42 }
/*
bupt 1032
nlogn LIS
注意!
是最长不减序列(*1),而非最长升序列(*2)
则当t>=D[len]就直接更新len+1
而t<D[len]时,应在D[1..len]中查找最大的j,满足D[j]<=A[t](在*2中,是满足D[j]<A[t]),
将t接在D[j]后得到更长的不减序列,同时更新D[j+1]=t
这是我WA很多次的地方.对这个算法未理解透彻
附一组原先错误程序WA的数据:
40
9 7 10 13 18 4 13 37 24 7 30 17 36 20 23 26 35 16 7 25 7 30 39 3 9 11 14 8 29 35 35 17 6 11 25 25 21 17 32 38
答案12
*/
#include <iostream>
using namespace std;
int T,N,m,cnt,r[50010];
int main(){
int i,j,k;
scanf("%d",&T);
while(T--){
scanf("%d",&N);
cnt=0; r[0]=-1;
for(i=1;i<=N;i++){
scanf("%d",&m);
if(m>=r[cnt]){ //not '>'
r[++cnt]=m;
}
else{
int bl=1,bh=cnt,bm;
k=-1;
while(bl<=bh){
bm=(bl+bh)/2;
if(r[bm]>m){ //not '>='
bh=bm-1;
k=bm;
}
else bl=bm+1;
}
r[k]=m;
}
}
printf("%d\n",cnt);
}
return 0;
}
http://acm.cs.bupt.cn/onlinejudge/showproblem.php?problem_id=1379
给一个长度10MB的大数n,要求计算ceil(n/2),内存只有1000K,显然不能开数组,要边读边除
通常的除法只要设个变量记录每位是否整除(mod).此外题目要求不输出前导0,再设个bool值记录(zero)
特殊之处在于向上取整.举个例子:1999/2=1000,显然直接除一位输出一位有问题
关键之处在于增加一个变量记录连续的9的个数(cnt9).如果处理到非9的位,或者输入文件结束,就分情况输出前面最近一位非9数除的结果,然后循环输出9除的结果.因此,还要一个变量记录上一位除得的商(co)
1 /*
2 记录连续9的个数,为了使输入末尾有连续9时向上取整
3 co记录上位除的商
4 mod记录上位除的余数
5 cnt9记录连续的9的个数
6 zero记录前导是否为0
7 当前位不是9时,输出之前的结果,并将当前位+mod*5存入co
8 当前位是9时,cnt9++
9 输入结束时,处理末尾几位
10 注意:
11 输入为0时
12 以9开头时
13 以x9开头时
14
15 几组数据:
16 000319900099 159950050
17 199 100
18 0199 100
19 1998 999
20 99 50
21 0 0
22 */
23 #include <iostream>
24 using namespace std;
25 int main(){
26 bool zero;
27 int mod,cnt9;
28 char co,cn,ct;
29 zero=true; mod=0; co=0; cnt9=0;
30 while(isdigit(cn=getchar())){
31 cn-='0';
32 if(cn!=9){
33 if(!zero||co){
34 zero=false;
35 putchar(co+'0');
36 }
37 if(cnt9)zero=false;
38 while(cnt9--){
39 putchar(4+5*mod+'0');
40 mod=1;
41 }
42 cnt9=0;
43 co=(cn>>1)+5*mod;
44 mod=cn&1;
45 }
46 else{
47 cnt9++;
48 }
49 }
50 if(!zero||co||mod){
51 zero=false;
52 putchar(co+mod+'0');
53 }
54 mod=1-mod;
55 if(cnt9)zero=false;
56 while(cnt9--){
57 putchar(5*mod+'0');
58 mod=0;
59 }
60 //输入0的情况!
61 if(zero)putchar('0');
62 putchar('\n');
63 return 0;
64 }
65
摘要: BFS实现，O(n^3)
Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1 #include <iostream> 2 using namespace...
阅读全文