摘要: 求所謂的 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 游覽路線
這樣可以得出算法的大致輪廓:在加入點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... 閱讀全文