久久爱www.,国产麻豆精品在线观看,亚洲国产二区

PKU 3164 Command Network 最��树形图

_飞寒 — Sun, 20 Feb 2011 13:05:00 GMT

题意�Q�要求徏立司令部到各个欧几里德��^面上的节点，�l�定可徏立的��点�?u,v) = u 可徏立单向信道至 v �Q�求��o部�Ş成对所有节点的指挥需要的最��徏设花贏V�?br> ��法�Q�最��图形树�Q�不解释~

1/*
2Problem: 3164        User: _mTy
3Memory: 872K        Time: 172MS
4Language: C++        Result: Accepted
5
6Source Code
7*/
8#include
9#include
10#include
11#define MAXN 120
12#define inf 1000000000
13typedef double elem_t;
14elem_t edmonds(int n,elem_t mat[][MAXN*2],int* pre);
15int main(){
16    elem_t point[MAXN][2];
17    elem_t mat[MAXN*2][MAXN*2];
18    elem_t res,len;
19    int pre[MAXN];
20    int i,j,n,m,u,v;
21
22    while(scanf("%d%d",&n,&m)!=EOF){
23        for(i=0;i<n;i++) for(j=0;j<n;j++) mat[i][j]=inf;
24        for(i=0;i<n;i++) scanf("%lf%lf",&point[i][0],&point[i][1]);
25        for(i=0;i<m;i++){
26            scanf("%d%d",&u,&v); --u; --v;
27            len = pow(point[u][0]-point[v][0],2)+pow(point[u][1]-point[v][1],2);
28
29            len = sqrt(len);
30            mat[u][v]=len;
31        }
32
33        memset(pre,0,sizeof(pre));
34        pre[0]=-1;
35        res = edmonds(n,mat,pre);
36        if(res<0) printf("poor snoopy\n");
37        else printf("%.2f\n",res);
38    }
39    return 0;
40}
41
42//多源最��树形图,edmonds��法,��L��阵�Ş�?复杂度O(n^3)
43//�q�回最��生成树的长�?构造失败返回负�?br>44//传入囄��大小n和邻接阵mat,不相�ȝ��Ҏ��inf
45//可更改边权的�c�d��,pre[]�q�回树的构�?用父�l�点表示
46//传入时pre[]数组清零,�?1标出源点
47
48elem_t edmonds(int n,elem_t mat[][MAXN*2],int* pre){
49    elem_t ret=0;
50    int c[MAXN*2][MAXN*2],l[MAXN*2],p[MAXN*2],m=n,t,i,j,k;
51    for (i=0;i<n;l[i]=i,i++);
52    do{
53        memset(c,0,sizeof(c)),memset(p,0xff,sizeof(p));
54        for (t=m,i=0;i<m;c[i][i]=1,i++);
55        for (i=0;i<t;i++)
56            if (l[i]==i&&pre[i]!=-1){
57                for (j=0;j<m;j++)
58                    if (l[j]==j&&i!=j&&mat[j][i]<inf&&(p[i]==-1||mat[j][i]<mat[p[i]][i]))
59                        p[i]=j;
60                if ((pre[i]=p[i])==-1)
61                    return -1;
62                if (c[i][p[i]]){
63                    for (j=0;j<=m;mat[j][m]=mat[m][j]=inf,j++);
64                    for (k=i;l[k]!=m;l[k]=m,k=p[k])
65                        for (j=0;j<m;j++)
66                            if (l[j]==j){
67                                if (mat[j][k]-mat[p[k]][k]<mat[j][m])
68                                    mat[j][m]=mat[j][k]-mat[p[k]][k];
69                                if (mat[k][j]<mat[m][j])
70                                    mat[m][j]=mat[k][j];
71                            }
72                    c[m][m]=1,l[m]=m,m++;
73                }
74                for (j=0;j<m;j++)
75                    if (c[i][j])
76                        for (k=p[i];k!=-1&&l[k]==k;c[k][j]=1,k=p[k]);
77            }
78    }
79    while (t<m);
80    for (;m-->n;pre[k]=pre[m])
81        for (i=0;i<m;i++)
82            if (l[i]==m){
83                for (j=0;j<m;j++)
84                    if (pre[j]==m&&mat[i][j]==mat[m][j])
85                        pre[j]=i;
86                if (mat[pre[m]][m]==mat[pre[m]][i]-mat[pre[i]][i])
87                    k=i;
88            }
89    for (i=0;i<n;i++)
90        if (pre[i]!=-1)
91            ret+=mat[pre[i]][i];
92    return ret;
93}

_飞寒 2011-02-20 21:05 发表评论

_飞寒 — Sun, 20 Feb 2011 05:48:00 GMT

判断一个无向连通图的MST是否唯一�Q�其实本质上��是求是否存在次��树恰好�{�于MST�?br> 16ms��过~ 数据弱，不徏议用来测试模版，据说有非SST做法�Q�kuskal + LCA + O(E) �Q�求大神教学……

1/*
2Problem: 1679        User: _mTy
3Memory: 760K        Time: 16MS
4Language: G++        Result: Accepted
5
6Source Code
7*/
8
9#include
10#include
11#include
12#include
13#define N 101
14using namespace std;
15
16struct nod{
17    int u,max;
18};
19int g[N][N];
20int tree[N][N];
21int best[N][N];
22
23int prim(int n,int fa[]);
24
25int main(){
26    int t,n,m;
27    int i,j,u,v,w,t1,total;
28    int fa[N];
29    struct nod tmp,arr[N*N];
30    bool unique,visi[N];
31    scanf("%d",&t);
32    while(t--){
33        scanf("%d%d",&n,&m);
34        for(i=0;i<n;i++) for(j=0;j<n;j++) g[i][j]=0x7fffffff;
35        memset(tree,-1,sizeof(tree));
36        for(i=0;i<m;i++){
37            scanf("%d%d%d",&u,&v,&w);
38            g[u-1][v-1]=g[v-1][u-1]=w;
39        }
40        t1=prim(n,fa);
41        for(i=0;i<n;i++) tree[i][fa[i]]=tree[fa[i]][i]=g[i][fa[i]];
42
43        // bfs
44        total=0;
45        memset(best,-1,sizeof(best));
46        for(i=0;i<n;i++){
47            memset(visi,0,sizeof(visi));
48            arr[total].u=i; arr[total].max=-1;
49            queue<struct nod> _que; _que.push(arr[total]); ++total;
50            visi[i]=1;
51            while(!_que.empty()){
52                tmp = _que.front(); _que.pop();
53                for(v=0;v<n;v++)
54                    if( !visi[v] && tree[tmp.u][v]!=-1 ){
55                       visi[v]=1;
56                       best[i][v]=
57                                (tmp.max<tree[tmp.u][v])?tree[tmp.u][v]:tmp.max;
58                       arr[total].max=best[i][v];
59                       arr[total].u=v;
60                       _que.push(arr[total]);
61                       ++total;
62                    }
63            }
64        }
65        unique = 1;
66        for(i=0;i<n;i++)
67            for(j=i+1;j<n;j++)
68                if( g[i][j]!=0x7fffffff && tree[i][j]==-1 )
69                    if( t1 - best[i][j] + g[i][j] == t1 ) unique = 0;
70
71        if( unique ) printf("%d\n",t1);
72        else printf("Not Unique!\n");
73
74    }
75
76    return 0;
77}

_飞寒 2011-02-20 13:48 发表评论

_飞寒 — Sun, 20 Feb 2011 05:39:00 GMT

查询和修改给定区间的颜色�U�类�Q�将一个区间的颜色�U�类k用二�q�制�?^k表达�Q�位�q�算求或卛_��得出��L��区间的不同颜色种�c�R�?br> 查询量巨大，��按线�D�|��斎ͼ�不要每次都更新到树叶�?br> 我也不明白我的程序怎么那么慢。。�?求xxms做法�?br>

1/*Source Code
2
3Problem: 2777        User: _mTy
4Memory: 4024K        Time: 329MS
5Language: C++        Result: Accepted
6
7*/
8#include<stdio.h>
9#include<string.h>
10#define MAXV 666666
11#define swap(a,b) a^=b^=a^=b
12
13typedef unsigned long _UL;
14typedef _UL ele_t;
15ele_t data[MAXV];
16int B[MAXV],E[MAXV],LSON[MAXV],RSON[MAXV],C[MAXV];
17int cnt;
18bool fill[MAXV];
19// B[] E[] 存放 [a,b]左界右界
20// C[] 覆盖当前区间的线�D�|��
21// LSON,RSON 点v的左叛_��子的数组下标
22//  fill[] 指示特定区间是否仅被一�U�颜色填�?/span>
23
24void ini(int u,int v){
25   int i;
26   ++cnt; i = cnt; B[i] = u; E[i] = v;
27   if( v - u >= 1 ){
28      LSON[i] = cnt+1; ini(u,(u+v)/2);
29      RSON[i] = cnt+1; ini((u+v)/2+1,v);
30   }
31}
32
33void insert(int u,int v,int r,ele_t ele){    // ��区间[u,v]信息 data 插入�?nbsp;r 为根的线�D�|��
34    if( u <= B[r] && v >= E[r] ){
35        data[r] = 1UL<<ele-1;
36        fill[r] = 1;
37    }else{
38        if( fill[r] == 1 ){ data[LSON[r]] = data[RSON[r]] = data[r]; fill[LSON[r]] = fill[RSON[r]] = 1; }
39
40        if( u <= (B[r]+E[r])/2 ) insert(u,v,LSON[r],ele);
41        if( v >= (B[r]+E[r])/2+1 ) insert(u,v,RSON[r],ele);
42
43        // updata [u,v]
44        data[r] = data[LSON[r]] | data[RSON[r]];
45        fill[r] = 0;
46    }
47}
48
49_UL out(int u,int v,int r){
50    int data_1 = 0,data_2 = 0;
51    if( fill[r] == 1 || u <= B[r] && v >= E[r] ) return data[r];
52    else{
53        if( u <= (B[r]+E[r])/2 ) data_1 = out(u,v,LSON[r]);
54        if( v >= (B[r]+E[r])/2+1 ) data_2 = out(u,v,RSON[r]);
55        return data_1 | data_2;
56    }
57}
58
59int main(){
60    int i,j,l,t,o,u,v,cc,res;
61    _UL val;
62    char chr;
63    while(scanf("%d%d%d",&l,&t,&o)!=EOF){
64        getchar();
65
66        data[1] = 1UL;
67        cnt = 0; ini(1,l);
68        memset(fill,0,sizeof(bool)*(cnt+1));  fill[1] = 1; // 初始区间 [u,v] �?颜色填充
69
70        for(i=0;i<o;i++){
71            scanf("%c%d%d",&chr,&u,&v);
72            if( u>v ) swap(u,v);
73            if( chr == 'C' ){
74                scanf("%d",&cc);
75                getchar();
76                insert(u,v,1,cc);
77            }else{
78                getchar();
79                val = out(u,v,1);
80                res = 0;
81                for(j=0;j<t;j++) if( val & 1UL<< j ) ++res;
82                printf("%d\n",res);
83            }
84        }
85    }
86    return 0;
87}

_飞寒 2011-02-20 13:39 发表评论

径向梯度变换

_飞寒 — Sat, 19 Feb 2011 13:53:00 GMT

�W�一个CV�E�序�Q�对囄��做径向梯度变换�?�U�念下~

1// HelloOpencv.cpp : 定义控制台应用程序的入口炏V�?/span>
2
3#include "stdafx.h"
4#include"cxcore.h"
5#include "highgui.h"
6#include<math.h>
7using namespace cv;
8using namespace std;
9
10int _tmain(int argc, _TCHAR* argv[])
11{
12    CvPoint center;
13    double scale = -3;
14    IplImage* image = (argc == 2 )? cvLoadImage(argv[1]) : 0;
15    if( ! image ) return -1;
16    center = cvPoint( image->width/2 , image->height/2 );
17    for( int i = 0; i<image->height; i++ )
18        for( int j = 0; j<image->width; j++ ){

19            double dx = ( double )( j-center.x )/center.x;
20            double dy = ( double )( i-center.y )/center.y;
21            double wight = exp( (dx*dx+dy*dy)*scale );
22            uchar* ptr = &CV_IMAGE_ELEM( image, uchar, i, j*3 );
23            ptr[0] = cvRound(ptr[0]*wight);
24            ptr[1] = cvRound(ptr[1]*wight);
25            ptr[2] = cvRound(ptr[2]*wight);
26        }
27    cvSaveImage("new.png",image);
28    cvNamedWindow("_飞寒�?nbsp;TEST",1);
29    cvShowImage("_飞寒�?nbsp;TEST",image);
30    cvWaitKey();
31    return 0;
32}
33
34

效果如下�Q?br>

_飞寒 2011-02-19 21:53 发表评论

_飞寒 — Sat, 19 Feb 2011 07:30:00 GMT

        在酝酿了半个月之后，鄙�h�l�于��磨�y�蹭的下载安装了CV2.2-win32版本。但�׃��下蝲到的是针对VS2010优化的，无法遇见安装�?008中会发生什么问题。终于在煎熬�?8��时+各种goole+自力更生后成功compiled~ 以下为安装流�E�，与CV2.1�?.0版本的安装原理大同小异，但由�?.2的文件组�l�结构发生变化，可能会导致像我这��L��白照抄步骤的话无法成功安装�Q?br>
      1. 下蝲安装OpenCV2.2��C�Q意西文�\径�?br>
      2. 下蝲安装 CMake 2.8 �Q�安装后用于导出CV的c++��目文�g�?br>            http://www.cmake.org/cmake/resources/software.html

      (1) 如图所�C?选择�~�译资源�Q�和�~�译后结果的保存路径(�?F:\OpenCV2.2\vc2008 )。点�?span class=Apple-style-span style="WORD-SPACING: 0px; FONT: medium Simsun; TEXT-TRANSFORM: none; COLOR: rgb(0,0,0); TEXT-INDENT: 0px; WHITE-SPACE: normal; LETTER-SPACING: normal; BORDER-COLLAPSE: separate; orphans: 2; widows: 2; webkit-border-horizontal-spacing: 0px; webkit-border-vertical-spacing: 0px; webkit-text-decorations-in-effect: none; webkit-text-size-adjust: auto; webkit-text-stroke-width: 0px">configure�Q�配�|��ؓ VS 9 2008�Q�配�|�无误后点击Generate生成各种工程文�g�?br>


         (2) 在编译结果的文�g夹内生成OpenCV.sln的VC Solution File�Q�请用VS 2008 打开OpenCV.sln, 然后全部�~�译�Q�无误后批生成所有EXAMPLE�?br>

       ��x��Q�OpenCV�?d.dll文�g�Q�for debug�Q�和*.dll文�g�Q�for release�Q�将出现�?\vs2008\bin 目录中；OpenCV�?d.lib文�g�Q�for debug�Q�和*.lib文�g�Q�for release�Q�将出现在\vs2008\lib 目录�Q�头文�g*.h出现�?vs2008\include\opencv2中。可以被 VS 2008 调用的OpenCV动态库

     (5) 配置�pȝ��环境变量 ��?..\vs2008\bin加入Windows�pȝ��环境变量Path中，可能要重启�?br>
     (6) 为VS2008配置 OpenCV环境�Q�如图，配置CV�E�序可能需要的库文件和头文件。到了这一步问题终于出��C��Q�按照CV中文站上的安装教�E�安装的话，VS死都提示 xxx.h 文�g无法扑ֈ�。经�q�多番摸索，最后是��定文�g�l�构造成的问题�?br>

     首先�Q�完全生成OpenCV.sln内的代码后，\vs2008\include �?\vs2008\lib 内会出现相应的文�Ӟ��.lib文�g的�\�?nbsp; xxx\vs2008\lib 只需按照教程直接��d��卛_��?br>但是include文�g则不同，�?.1及其以下版本中的文�g�l�织方式不同�Q?.2中由于一些重大更斎ͼ�在opencv文�g夹同�U�目录下拥有opencv2文�g�?未��用VS08批生成之�?�Q�所有相应的头文件其实都已经�q�入其中�Q�保留opencv文�g夹的目的是�ؓ了向下兼容，打开opencv文�g多w��的�Q意头文�g�Q�我们发��C��码处大致�?

#ifndef __OPENCV_OLD_CXCORE_H__
#define __OPENCV_OLD_CXCORE_H__

//#if defined(__GNUC__)
//#warning "This is a deprecated opencv header provided for compatibility. Please include a header from a corresponding opencv module"
//#endif

#include "opencv2/core/core_c.h"
#include "opencv2/core/core.hpp"

#endif

实际上编译被跌��{了，但是回到 \vs2008\inlcude目录下，惊讶的发现生成的�l�果事实上未包含 opencv文�g夹！此时如果仅仅�?...\vs2008\include\opencv2配置�Q�则vs2008仍然无法导入头文�Ӟ��此时需要手动将 \include\opencv 目录复制�?\vs2008下，然后�q�加配置 ...\vs2008\include\opencv。最后F5�~�译�Q�bingo~

_飞寒 2011-02-19 15:30 发表评论

PKU 1836 Alignment 枚�D+LIS

_飞寒 — Mon, 14 Feb 2011 08:51:00 GMT

题意�Q�一个士兵列队，因�ؓ高度��D��参差不齐�Q�长官要求最��k个�h出列�Q��得剩下的人在不改变相�Ҏ��序的情况下，保证从左到右的高度保证严格满��?a1ai+2>ai+3>...>an�?/p>

上面�q�条表达式出来之后就很容易想到LIS了，也就是枚举ai和ai+1的位�|�，然后左半部分和又半部分分别往相反的方向做LIS�Q�求出出列数最短的一个中点即可，其中做LIS可以采用二分查找�Q��得�{�U�花费从O(n)降�ؓO(lg n)�?br>

1#include<cstdio>
2#include<cstring>
3#define inf 0x7fffffff
4#define N 1001
5#define MAX(a,b) (a
6#define MIN(a,b) (a
7using namespace std;
8int lis[N],lds[N];
9double w[N];
10
11int find(double c[],int len,double k){
12    int left=0,right=len,mid=(left+right)/2;
13    while(left<=right){
14        if( k>c[mid] ) left=mid+1;
15        else if( k<c[mid] ) right=mid-1;
16            else { return mid; }
17        mid=(left+right)/2;
18    }
19    return left;
20}
21
22int main(){
23    int n,i,j,res;
24    int tmpDp[N];
25    double c[N];
26    while(scanf("%d",&n)!=EOF){
27        for(i=0;i<n;i++) scanf("%lf",&w[i]);
28
29        for(i=0;i<=n;i++) c[i]=inf;
30        c[0]=-1; c[1]=w[n-1];
31        memset(tmpDp,0,sizeof(tmpDp));
32        tmpDp[n-1]=1;
33        for(i=n-2;i>-1;--i){
34            j=find(c,n+1,w[i]);
35            c[j]=w[i]; tmpDp[i]=j;
36        }
37        for(j=-1,i=n-1;i>-1;--i){ j=MAX(j,tmpDp[i]); lds[i]=j; }
38
39        for(i=0;i<=n;i++) c[i]=inf;
40        c[0]=-1; c[1]=w[0];
41        memset(tmpDp,0,sizeof(tmpDp));
42        tmpDp[0]=1;
43        for(i=1;i<n;++i){
44            j=find(c,n+1,w[i]);
45            c[j]=w[i]; tmpDp[i]=j;
46        }
47        for(j=-1,i=0;i<n;++i){ j=MAX(j,tmpDp[i]); lis[i]=j; }
48
49        res=inf;
50        for(i=0;i<n;++i){
51            res=MIN(res,n-(lis[i]+lds[i+1]));
52        }
53        printf("%d\n",res);
54    }
55    return 0;
56}

_飞寒 2011-02-14 16:51 发表评论

PKU 3267 The Cow Lexicon 字符串DP

_飞寒 — Sat, 12 Feb 2011 12:56:00 GMT

    Few know that the cows have their own dictionary with W (1 ≤ W ≤ 600) words, each containing no more 25 of the characters 'a'..'z'. Their cowmunication system, based on mooing, is not very accurate; sometimes they hear words that do not make any sense. For instance, Bessie once received a message that said "browndcodw". As it turns out, the intended message was "browncow" and the two letter "d"s were noise from other parts of the barnyard.
    The cows want you to help them decipher a received message (also containing only characters in the range 'a'..'z') of length L (2 ≤ L ≤ 300) characters that is a bit garbled. In particular, they know that the message has some extra letters, and they want you to determine the smallest number of letters that must be removed to make the message a sequence of words from the dictionary.

       开始的时候觉得很难，后来仔细思考之后才发现切入点，重要的还是看��Z��个合适的子问题，��M��DP题目��得多练才能出眼光�?br>       设dp[i]为前i个字�W��{为合法所需删除的字母个敎ͼ�那么当我们递推dp[i+1]的时候，实际上就是尝试寻找一个字兔R��的串�Q�它也以sourc[i+1]收尾(有的做法是以i字母打头往前推)�Q�那么这时候dp[i+1]需要知道的��是 dp[i-(cnt+w[j])]处的�l�果�Q�cnt+w[j]是倒退的长度，�q�个长度包含了某个合法串长度w[j]和cnt个被删除的字�W�，此时推得一个��时解�Q�所有字典单词推出的临时解中最��的一个�{�U�M��?br>      转移方程�Q�DP[i]=Min{ DP[i] ,DP[i-(cnt+w[k])]+cnt ,DP[i-1]+1 }

1#include<iostream>
2#include<cstring>
3using namespace std;
4#define MIN(a,b) (a
5#define L 301
6#define W 601
7int dp[L];
8int lenArr[W];
9char sourc[L+1];
10char dic[W][27];
11int main(){
12    int i,j,k;
13    int l,w;
14    int souPoi,dicPoi,cnt;
15    while(cin>>w>>l){
16        cin>>sourc;
17        for(i=0;i<w;i++){ cin>>dic[i]; lenArr[i]=strlen(dic[i])-1; }
18
19        for(i=0;i<=l;i++) dp[i]=0x7fffffff;
20        dp[0]=0;
21        for(i=1;i<=l;i++){
22            for(j=0;j<w;j++){
23                dicPoi=lenArr[j];
24                souPoi=i-1;
25                cnt=0;
26                /* 倒退匚w��Q�若当前不匹配，则尝试删��M��个字�W?nbsp;*/
27                while( souPoi>-1 && dicPoi>-1 ){
28                    if( sourc[souPoi] == dic[j][dicPoi] ){ --souPoi; --dicPoi; }
29                    else{ ++cnt; --souPoi; }
30                }
31                if( dicPoi<0 ){ dp[i]=MIN(dp[i],dp[i-(cnt+lenArr[j]+1)]+cnt); }
32                else{ dp[i]=MIN(dp[i],dp[i-1]+1); }   /* 匚w��p�| */
33            }
34        }
35
36        printf("%d\n",dp[l]);
37    }
38    return 0;
39}

_飞寒 2011-02-12 20:56 发表评论

PKU 1882 Stamps 背包变�Ş

_飞寒 — Fri, 11 Feb 2011 12:20:00 GMT

摘要: Description Philatelists have collected stamps since long before postal workers were disgruntled. An excess of stamps may be bad news to a country's postal service, but good news to those that collec... 阅读全文

_飞寒 2011-02-11 20:20 发表评论

_飞寒 — Fri, 04 Feb 2011 07:17:00 GMT

Tarjan��法�Q?/p>

　 �q�是SCC问题的第一个算法，由Tarjan�?972�q�提出。算法仍然借助DFS�Q�但它�ƈ不依靠遍历顺序来把不同的SCC分离��C��同的DFS树中�Q�而是让多个SCC�q�存于同一个DFS树中�Q�用某种手段把他们分开。考虑一个强分量C�Q�设其中�W�一个被发现的点为x�Q�由白�\径定理，C中其他点都是x的后代。我们希望在x讉K��完成时立刻输出C�?注意�q�里是一个严格的数学描述)。这��P��可以在同一��DFS树中区分开所有的SCC了。因此问题的关键是：如何判断一个点是否为SCC中最先被发现的点�?br>　
　   如图�?img style="WIDTH: 384px; HEIGHT: 259px" border=0 alt=dfs�?align=right src="http://m.shnenglu.com/images/cppblog_com/mtysblog/Tarjan.jpg" width=384 height=259>假设我们正在判断u是否为某SCC中第一个被发现的节炏V��如果我们发��C��u的儿子出发可以到达u的祖先w,昄��u\v\w在同一个SCC中，因此u不是该SCC�W�一个被发现的节炏V��如果从v出现最多只能到u�Q�那么u是该SCC中第一个被发现的节点（也许有同学会问，若所有子节点不能到达u本��n�Q�何以能说明u是和子树��通的�Q�其实由于DFS的特点，若这��L��情况出现�Q�实际上在u的子树上已经完成了一个强分量的寻找，u此时是只到它本��n�?#8220;�W�一�?#8221;被发现节点，原书的描�q�是严格和归�U�的�Q�。这��P��问题转化为求�Q�一个点u最�q�能到达的祖先的d倹{��注意这里的“到达”可以通过后向�Ҏ��交叉边，但是前提是只能通过栈里面的点而不是已�l�确定SCC�~�号的其他点。图中实�U�表�C�Z��条边�Q�虚�U�表�C�Z��条或多条辏V�?br>

      定义low[u]为u及其后代能追溯到的最早祖先v的发现时间戳pre[v]�Q�我们可以在计算low函数的同时完成SCC的计��，low函数的递推�Ҏ��如下�Q?br>      利用全局栈_sta保存当前SCC中的节点�Q�注意栈中节点�Ş成树而不一定是链）�Q�cnt为开发当前点u的时间戳�Q�scnt为强分量�~�号器，id[]为强分量�~�号数组�?br>
      原始的Tarjan��法递推方式为：如果 pre[w]

1void dfs-scc(int u){
2    int w,min;
3    min=low[u]=pre[u]=cnt++;
4     /* 初始化时间戳�Q�low��|��子节�Ҏ��祖�?nbsp;为当前时间戳 */
5     _sta.push(u);
6
7     for each (u,w){
8         if(pre[w]==-1) dfs-scc(w);
9         /* 未开发节�?nbsp;*/
10         if( low[w]<min ) min=low[w];
11         /* 求出u所有儿子i最�q�能到达的祖�?nbsp;*/
12     }
13
14     if(min<low[u]){ low[u]=min; return ; }
15     /* 所有的儿子能到辄��最�q�祖先是u的祖先，因此u不是SCC
16         �W�一个被发现的节点，通过子节点，u应能到达�q�样的第一个节�?nbsp;*/
17     do{
18         w=_sta.pop(w);
19         id[w]=scant;
20         low[w]=0x7fffffff; /* 锁定low�Q�保证w不会被其他强分量吸收 */
21     }while(w!=u)
22     /* 此时�Q�u的所有子节点必能且最�q�仅能到达u�Q�他们沟通构成一个SCC */
23     scant++;
24}

_飞寒 2011-02-04 15:17 发表评论

_飞寒 — Thu, 03 Feb 2011 04:11:00 GMT

摘要: 哥�ؓ了来�q�交�q�好�q�，大年三十特地上来刯��题，�l�果��p��疼到�?1�Q?0才写完，不过很高兴能�?A�Q�希望今�q�事事顺利！题目要求对一个给定的自然敎ͼ�求出一个符合规定的的降序列�Q�这个规则就是每�ơ从数列前一��减��d��个数位，而这几个��C��构成�?#8220;合法自然�?... 阅读全文