misschuer

常用链接

统计

积分与排名

百事通

最新评论

hdu 3686 Traffic Real Time Query System

 1这个做了一个月居然意思都没有理解, 最后认认真真读了一遍原来意思是求一条路(u1, v1)到另一条路(u2, v2)所要经过的最小割点数,原来表示一直以为是点u到点v要经过的最小割点数(对这种情况我居然还傻傻的判断了点u或点v是割点的情况无奈一直WA);
 2
 3先求点的双连通分量,然后把一个双连通分量(不包括割点)看成一个点,所以这个连通分量的所有边都是这个连通分量的标号,
 4然后把每个割点也看成一个点(定义一个编号),构图;
 5eg.
 65 6
 71 2
 81 3
 92 3
103 4
114 5
123 5
13
14分量1有 1, 2, 3
15分量2有 3, 4, 5
16所以边(1,2), (1,3), (2,3)是1
17(3 4),(4 5),(3 5)      是2
18割点3                    是3
19
20构图 
21连接(13), (23)
22然后求出编号之间的最短距离/2即是答案
23eg
242
252 3
262 4
27
28对于2 3
29第2条属于1
30第3条属于1
311-1的最短距离为0,在同一个连通分量内所以距离为0
32
33对于2 4
34第2条属于1
35第4条属于2
361-2的最短距离为2,所以距离为2/2=1;
37代码很挫就不贴

int main() {
    
    int n, m;
    int i, j, Q;
    while(cin >> n >> m) {
        
        if(n == 0 && m == 0) break;
        b_sn = 0;
        memset(dfn, -1, sizeof(dfn));
        memset(low, 0, sizeof(low));
        memset(belong, -1, sizeof(belong));
        memset(p, -1, sizeof(p));    
        memset(fa, -1, sizeof(fa));
        memset(in, false, sizeof(in));
        memset(re, false, sizeof(re));
        eid = 0;  cnt = 0;
        memset(road, -1, sizeof(road));
        while(!S.empty()) S.pop();
        
        for(i = 0; i <= n; ++ i) {
        
            b_con[ i ].clear();//编号为i的联通分量包含的点
            block[ i ].clear();//点i属于的联通分量编号,割点的话有2分量
        }
        
        for(i = 1; i <= m; ++ i) {
            
            int u, v;
            cin >> u >> v;
            
              add(u, v, i);
              add(v, u, i);        
        }

        for(i = 1; i <= n; ++ i) if(dfn[ i ] == -1) dfscutp(i);
        
        eid = 0;
        memset(p, -1, sizeof(p));
        memset(fa, -1, sizeof(fa));


        for(i = 1; i <= n; ++ i) {
        
            if(block[ i ].size() > 1) {
            
                ++ b_sn;
                belong[ i ] = b_sn;
                for(j = 0; j < block[ i ].size(); ++ j) {
                
                    int v = block[ i ][ j ];
                    
                    add(b_sn, v, 1);
                    add(v, b_sn, 1);
                }
            }
        }

        qid = 0;
        memset(pq, -1, sizeof(pq));
        cin >> Q;
        memset(vist, false, sizeof(vist));
        for(i = 1; i <= Q; ++ i) {
        
            int u, v;
            scanf("%d %d", &u, &v);
            
            u = road[ u ];
            v = road[ v ];
 
            if(u == v) ans[ i ] = 0;
            else {
                
                addQ(u, v, i);
                addQ(v, u, i);
            }
        }

        for(i = 1; i <= b_sn; ++ i) {
        
            if(!vist[ i ]) tarjan(i, 0);
        }

        for(i = 1; i <= Q; ++ i) {
        
            printf("%d\n", ans[ i ] / 2);
        }
    }
        
    return 0;
}

posted on 2011-05-16 16:45 此最相思 阅读(412) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理