频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
lightoj1086 - Jogging Trails(状态压缩dp)
2013-11-28 11:34:49      个评论      
收藏   我要投稿
一道有点小思维的状态压缩dp

 

题意:给出n个点,m条边的一幅无向图,n<=15,m<=3000。问,从任意点出发,每条边至少走过一次,再回到起点,至少要走多少路。

 

解题思路:问题问的是,从起点出发,每条边至少走一次,然后又要回到这个点,那么,每个点也肯定至少被走到一次吧,这不就是一个欧拉回路吗?也就是说,这些边至少用到一次,去构造一个欧拉回路至少要多长距离咯。要构成欧拉回路,条件是每个点的度数为偶数,既然每条边都至少要走一次,那么就先把每条边加进来一次,然后统计一下加完之后的度数。根据图论握手定理的推论,无向图的奇度点必然是偶数个(想想也知道了),那么我们就每次拿出奇数度的两个点,构造一条新的边,把这两个点的度变为偶数,直到所有的点都是偶数度为止,这里用状态压缩就行了。然后就是两个奇度点之间新的一条边怎么构造了,很简单,floyd跑一遍就好了。这条新构造的边必然是最短的,而新加进来的边,也不会改变这条路径上的其他的度得奇偶性(路径上的其他点肯定是一进一出)。

 

代码:

 

  1

  2

  3

  4

  5

  6

  7

  8

  9

 10

 11

 12

 13

 14

 15

 16

 17

 18

 19

 20

 21

 22

 23

 24

 25

 26

 27

 28

 29

 30

 31

 32

 33

 34

 35

 36

 37

 38

 39

 40

 41

 42

 43

 44

 45

 46

 47

 48

 49

 50

 51

 52

 53

 54

 55

 56

 57

 58

 59

 60

 61

 62

 63

 64

 65

 66

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <map>

#include <queue>

#include <vector>

#include <string>

#include <iostream>

using namespace std;

 

const int INF = 111111111 ;

int l[22][22] , du[22] ;

int sum , dp[1<<20] ;

 

int main() {

    int n , m , i , j , k ;

    int t , ca = 0 ;

    scanf ( "%d" , &t ) ;

    while ( t -- ) {

    //    if ( n == 0 ) break ;

        scanf ( "%d%d" , &n , &m ) ;

        for ( i = 0 ; i < n ; i ++ ) {

            du[i] = 0 ;

            for ( j = 0 ; j < n ; j ++ )

                l[i][j] = INF ;

            l[i][i] = 0 ;

        }

        sum = 0 ;

        for ( i = 1 ; i <= m ; i ++ ) {

            int a , b , c ;

            scanf ( "%d%d%d" , &a , &b , &c ) ;

            a -- , b -- ;

            l[a][b] = l[b][a] = min ( l[a][b] , c ) ;

            du[a] ++ , du[b] ++ ;

         //   printf ( "du[%d] = %d" , a , du[a] ) ;

         //   printf ( "du[%d] = %d\n" , b , du[b] ) ;

            sum += c ;

        }

        for ( k = 0 ; k < n ; k ++ )

            for ( i = 0 ; i < n ; i ++ )

                for ( j = 0 ; j < n ; j++ )

                    l[i][j] = min ( l[i][j] , l[i][k] + l[k][j] ) ;

        int tot = 1 << n ;

        for ( i = 0 ; i < tot ; i ++ ) dp[i] = INF ;

        int p = 0 ;

        for ( i = n - 1 ; i >= 0 ; i -- ) {

            p <<= 1 ;

            if ( du[i] & 1 ) {

                p |= 1 ;

            //    printf ( "du[%d] = %d\n" , i , du[i] ) ;

            }

        }

   //     printf ( "p = %d\n" , p ) ;

        dp[p] = sum ;

        for ( i = tot - 1 ; i >= 0 ; i -- )

            for ( j = 0 ; j < n ; j ++ ) {

                if ( !( i & ( 1 << j ) ) ) continue ;

                for ( k = 0 ; k < n ; k ++ ) {

                    if ( j == k || !( i & ( 1 << k ) ) ) continue ;

                    dp[i^(1<<j)^(1<<k)] = min ( dp[i^(1<<j)^(1<<k)] , dp[i] + l[j][k] ) ;

                }

            }

        printf ( "Case %d: %d\n" , ++ ca , dp[0] ) ;

    }

    return 0 ;

}

点击复制链接 与好友分享!回本站首页
相关TAG标签 状态
上一篇:scrollview的一些代理方法
下一篇:串口中怎样接收一个完整数据包的解析
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站