程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 3812 Sea Sky 深搜+剪枝

hdu 3812 Sea Sky 深搜+剪枝

編輯:C++入門知識

題目意思:

從sea 找一條道sky 的最長路

題解:

先進行一系列的預處理

1。將所有不重復的字符串先保留下來,然後從小到大排序,這樣深搜的時候最先弄出來的答案就是最小的 字母序。

2. 進行深度優先搜索保留答案

3. 剪枝:

(1) 要注意sea sky 不存在的情況

(2) 要主要不連通情況

(3) 強力剪枝 不解釋了。


#include
#include
#include
#include
#include
#include
using namespace std;
char real[105][30];
int n,w=0,mm[105][105],st,et;
char temp1[208][30];
int record[105],vis[105],vis1[105];
int yes[105],root[105];

int Find(int r)
{
    if(r==root[r]) return r;
    else return root[r]=Find(root[r]);
}

int add(char *a)
{
    int i;
    for(i=0;i0){
                char temp[30];
                strcpy(temp,real[j]);
                strcpy(real[j],real[i]);
                strcpy(real[i],temp);
            }
        }
        for(i=0;i=w) return 0;
    int i;
    vis[now]=1;
    record[tt]=now;
    if(now==et){
        if(ansl

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved