青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

oyjpArt ACM/ICPC算法程序設計空間

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6

PKU1734 Sightseeing trip (CEOI99)

Posted on 2007-05-28 23:41 oyjpart 閱讀(2381) 評論(3)  編輯 收藏 引用 所屬分類: ACM/ICPC或其他比賽
很久沒寫結題報告了
今天做Sightseeing trip 上來貼個
Ural:1004

Sightseeing trip
Time Limit:1000MS  Memory Limit:65536K
Total Submit:317 Accepted:133 Special Judged

Description
There is a travel agency in Adelton town on Zanzibar island. It has decided to offer its clients, besides many other attractions, sightseeing the town. To earn as much as possible from this attraction, the agency has accepted a shrewd decision: it is necessary to find the shortest route which begins and ends at the same place. Your task is to write a program which finds such a route.

In the town there are N crossing points numbered from 1 to N and M two-way roads numbered from 1 to M. Two crossing points can be connected by multiple roads, but no road connects a crossing point with itself. Each sightseeing route is a sequence of road numbers y_1, ..., y_k, k>2. The road y_i (1<=i<=k-1) connects crossing points x_i and x_{i+1}, the road y_k connects crossing points x_k and x_1. All the numbers x_1,...,x_k should be different.The length of the sightseeing route is the sum of the lengths of all roads on the sightseeing route, i.e. L(y_1)+L(y_2)+...+L(y_k) where L(y_i) is the length of the road y_i (1<=i<=k). Your program has to find such a sightseeing route, the length of which is minimal, or to specify that it is not possible,because there is no sightseeing route in the town.

Input
The first line of input contains two positive integers: the number of crossing points N<=100 and the number of roads M<=10000. Each of the next M lines describes one road. It contains 3 positive integers: the number of its first crossing point, the number of the second one, and the length of the road (a positive integer less than 500).

Output
There is only one line in output. It contains either a string 'No solution.' in case there isn't any sightseeing route, or it contains the numbers of all crossing points on the shortest sightseeing route in the order how to pass them (i.e. the numbers x_1 to x_k from our definition of a sightseeing route), separated by single spaces. If there are multiple sightseeing routes of the minimal length, you can output any one of them.

Sample Input

5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20

 

Sample Output

1 3 5 2

 

點數是100個 題目意思是找一個最小權圈 以任意序輸出
從圖論的角度上考慮 應該是任意選一條邊(枚舉) 然后刪除邊 再以一個點為原點求Dijkstra 找出最小權圈 o(M*N^2)的復雜度 一個更加好的算法是限定枚舉的點為圈內序號最大的點 這樣就避免了對一個圈的多次枚舉(參考程序3)
如果直接搜就是任選一個點開始走回到原點則記錄長度 搜的時候必須要先對每個點的邊按照邊權進行排序 以備后面大量剪枝

程序1

 1//Solution
 2//by oyjpArt
 3//Algorithm:Search
 4#include <vector>
 5#include <iostream>
 6#include <algorithm>
 7using namespace std;
 8
 9const int N = 101;
10struct Node {int x, w; void set(int xx, int ww) {x =xx; w = ww; }};
11vector<Node> adj[N];
12int nv, ne, ans[N], na, S, rec[N];
13bool chk[N];
14int best;
15
16bool operator<(const Node& a, const Node& b) {
17 return a.w < b.w;
18}
19
20void search(int x, int sum, int depth, int father) {
21 int i;
22 if(x == S && chk[x]) {
23  if(sum < best) {
24   best = sum;  na = depth;
25   for(i = 0; i < depth; i++) ans[i] = rec[i];
26  }
27  return;
28 }
29 rec[depth] = x;
30 for(i = 0; i < adj[x].size(); ++i) if(adj[x][i].x != father) if(!chk[adj[x][i].x] || adj[x][i].x == S) {
31  chk[adj[x][i].x] = 1;
32  if(sum + adj[x][i].w < best) search(adj[x][i].x, sum + adj[x][i].w, depth+1, x);
33  chk[adj[x][i].x] = 0;
34 }
35
36
37int main() {
38 scanf("%d %d"&nv, &ne);
39 int i, u, v, w;
40 Node now;
41 for(i = 0; i < ne; i++) {
42  scanf("%d %d %d"&u, &v, &w);
43  --u; --v;
44  now.set(v, w);
45  adj[u].push_back(now);
46  now.x = u;
47  adj[v].push_back(now);
48 }
49 for(i = 0; i < nv; ++i) 
50  sort(adj[i].begin(), adj[i].end());
51 
52 best = 123456789;
53 for(i = 0; i < nv; ++i) {
54  memset(chk, 0, nv * sizeof(bool));
55  S = i;
56  search(i, 00-1);
57 }
58
59 if(best == 123456789) { printf("No solution.\n"); return 0; }
60 printf("%d", ans[0]+1);
61 for(i = 1; i < na; ++i) printf(" %d", ans[i]+1); putchar('\n');
62
63 return 0;
64}
65
66



程序2

 1//Solution
 2//by oyjpArt
 3//Algorithm : Enumerate + Dijkstra
 4#include <stdio.h>
 5#include <string.h>
 6
 7const int N = 101, M = 20001, MAXINT = 2000000000;
 8int ne, nv;
 9struct E {
10 int x, w; E* next;
11 void set(int xx, int ww, E* nn) {x = xx; w = ww; next = nn;}
12}e[M], * head[N];
13int best, dist[N], q[N], ans[N], pre[N], na;
14bool chk[N];
15
16void Dijk(int st, int endint ow) {
17 memset(chk, 0, sizeof(chk));
18 memset(dist, -1, sizeof(dist));
19 int qe = 1, qs = 0, i;
20 E * p;
21 for(i = 0; i < nv; ++i) if(i != st) {
22  for(p = head[st]; p != NULL; p = p->next) {
23   if(p->== i && p->> 0 && (dist[i] == -1 || dist[i] > p->w ) ) 
24    dist[i] = p->w;
25  }
26  if(dist[i] == -1) dist[i] = MAXINT;
27 }
28 q[0= st;
29 dist[st] = 0;
30 chk[st] = 1;
31 for(i = 0; i < nv; ++i) pre[i] = st;
32 pre[st] = -1;
33 while(qs < qe) {
34  int cur = q[qs++];
35  chk[cur] = 1;
36  if(ow + dist[cur] >= best) return;
37  if(cur == end) {
38   if(dist[end+ ow < best) {
39    na = 0;
40    for(i = cur; i != -1; i = pre[i]) ans[na++= i;
41    best = dist[end+ ow;
42   }
43   return;
44  }
45  int _min = MAXINT, mini = -1;
46  for(i = 0; i < nv; i++if(!chk[i]) {
47   if(dist[i] < _min) {
48    _min = dist[i];
49    mini = i;
50   }
51  }
52  if(mini == -1) return;
53  q[qe++= mini;
54  for(i = 0; i < nv; ++i) if(!chk[i]) {
55   for(p = head[mini]; p != NULL; p = p->nextif(p->== i)  break;
56   if(p == NULL) continue;
57   if(p->> 0 && p->+ dist[mini] < dist[i]) {
58    dist[i] = p->+ dist[mini];
59    pre[i] = mini;
60   }
61  }
62 }
63}
64
65int main() {
66 scanf("%d %d"&nv, &ne);
67 memset(head, NULL, nv * sizeof(E*));
68 int i, u, v, w;
69 for(i = 0; i < ne; ++i) {
70  scanf("%d %d %d"&u, &v, &w);
71  --u; --v;
72  e[2*i].set(u, w, head[v]);
73  head[v] = &e[2*i];
74  e[2*i+1].set(v, w, head[u]);
75  head[u] = &e[2*i+1];
76 }
77 E * p, * q;
78 best = MAXINT;
79 for(i = 0; i < nv; ++i) {
80  for(p = head[i]; p != NULL; p = p->next) {
81   int w = p->w;
82   int j = p->x;
83   for(q = head[i]; q != NULL; q = q->nextif(q->== j) q->= -q->w;
84   for(q = head[j]; q != NULL; q = q->nextif(q->== i) q->= -q->w;
85   Dijk(i, j, w);
86   for(q = head[i]; q != NULL; q = q->nextif(q->== j) q->= -q->w;
87   for(q = head[j]; q != NULL; q = q->nextif(q->== i) q->= -q->w;
88  }
89 }
90 if(best == MAXINT) printf("No solution.\n");
91 else {
92  printf("%d", ans[0+ 1);
93  for(i = 1; i < na; ++i) printf(" %d", ans[i] + 1); putchar('\n');
94 }
95 return 0;
96}
97//唉 不用vector代碼量增大好多。。暈倒
98

程序3:
經wywcgs大牛提醒 改寫成了Floyd程序 時間銳減
 1#include <stdio.h>
 2#include <string.h>
 3
 4const int N = 101;
 5const int MAXINT = 123456789;
 6int ne, nv;
 7int adj[N][N];
 8int pre[N][N];
 9int conn[N][N];
10int na, ans[N];
11int best;
12
13void floyd() {
14    int i, j, k, tmp, p;
15    for(k = 0; k < nv; ++k) {
16        for(i = 0; i < k; ++i) {
17            for(j = 0; j < k; ++j) if(conn[i][k] && conn[k][j] && j != i) {
18                if( (tmp = adj[i][j] + conn[k][i] + conn[j][k]) < best) {
19                    best = tmp;
20                    na = 1; ans[0= k; p = i;
21                    while(p != -1) {
22                        ans[na++= p;
23                        p = pre[p][j];
24                    }
25                }
26            } 
27        }
28        for(i = 0; i < nv; ++i) 
29            for(j = 0; j < nv; ++j) {
30                if(adj[i][j] > adj[i][k] + adj[k][j]) {
31                    adj[i][j] = adj[i][k] + adj[k][j];
32                    pre[i][j] = pre[i][k];
33                }
34            }
35    }
36}
37
38int main() {
39    int i, j, u, v, w;
40    memset(pre, -1, sizeof(pre));
41    scanf("%d %d"&nv, &ne);
42    for(i = 0; i < nv; ++i) {
43        for(j = i+1; j < nv; ++j) 
44            adj[i][j] = adj[j][i] = MAXINT;
45        adj[i][i] = 0;
46    }
47    for(i = 0; i < ne; ++i) {
48        scanf("%d %d %d"&u, &v, &w);
49        --u; --v;
50        if(w < adj[u][v])     
51            conn[u][v] = conn[v][u] = adj[u][v] = adj[v][u] = w;
52        pre[u][v] = v, pre[v][u] = u;
53    }
54    best = MAXINT;
55    floyd();
56    if(best == MAXINT) printf("No solution.\n");
57    else {
58        for(i = 0; i < na; ++i) {
59            printf("%d", ans[i] + 1);
60            if(i != na-1) putchar(' ');
61            else putchar('\n');
62        }
63    }
64
65    return 0;
66}
67

Feedback

# re: PKU1734 Sightseeing trip (CEOI99)  回復  更多評論   

2007-05-30 22:08 by wywcgs
呃……這道題有O(V^3)做法……一次floyd或者V次dijkstra……
你可以再想想,總之不是很難……

# re: PKU1734 Sightseeing trip (CEOI99)  回復  更多評論   

2007-07-28 17:27 by dingyihamigua
大牛人啊!!
很經典的東西!!
謝謝了哈!
辛苦了!!

# re: PKU1734 Sightseeing trip (CEOI99)  回復  更多評論   

2011-11-10 15:58 by wuyiqi
我感覺如果用搜索的話好像排序與不排序是一樣的吧,因為一個點是等可能的搜向鄰邊的,排序改變不了什么,就算先搜到最短的鄰邊,隨后還是有可能越走越遠
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            久久九九精品| 蜜桃av一区| 国产精品视频一区二区高潮| 亚洲一区二区在线看| 一区二区三区色| 国产精品日本| 免费成人毛片| 欧美精品一区三区| 午夜精品免费视频| 欧美在线视频二区| 亚洲激情网址| 国产精品99久久99久久久二8| 国产精品视频专区| 欧美aaaaaaaa牛牛影院| 欧美顶级艳妇交换群宴| 亚洲欧美日韩一区二区| 久久久国产精品一区二区三区| 亚洲黄一区二区三区| 99国产精品久久久久久久久久| 国产手机视频精品| 亚洲国产成人精品女人久久久 | 欧美国产欧美亚洲国产日韩mv天天看完整| 久久九九精品| 亚洲砖区区免费| 久久婷婷久久一区二区三区| 亚洲视频在线观看| 久久久www成人免费无遮挡大片| 亚洲日本中文| 午夜精品久久久久久久久| 亚洲茄子视频| 小黄鸭视频精品导航| 一区二区高清在线观看| 久久久精品免费视频| 亚洲欧美日韩一区| 欧美精品国产一区| 米奇777超碰欧美日韩亚洲| 国产精品久久久久久五月尺| 欧美激情精品久久久久久蜜臀| 国产欧美日韩综合一区在线观看 | 亚洲欧美国产77777| 夜夜嗨网站十八久久| 久久久久久亚洲综合影院红桃| 午夜精品久久| 欧美日韩免费观看一区=区三区| 免费观看成人www动漫视频| 国产精品美腿一区在线看| 亚洲激情综合| 亚洲黄色视屏| 久久综合九色综合网站| 久久午夜电影| 国产一区再线| 性欧美暴力猛交另类hd| 性久久久久久久| 欧美日韩国产在线播放网站| 欧美激情aaaa| 亚洲国产精品女人久久久| 久久国产精品黑丝| 久久久久国产一区二区三区| 国产精品一卡二卡| 亚洲免费在线观看| 欧美一区二区网站| 国产欧美日韩91| 篠田优中文在线播放第一区| 欧美一级网站| 国产日韩欧美a| 欧美在线一二三四区| 久久久最新网址| 精品福利电影| 老司机一区二区三区| 亚洲大胆av| 99精品欧美一区| 欧美日韩在线综合| 亚洲视频在线观看视频| 性色一区二区| 精品动漫3d一区二区三区| 久久久久一本一区二区青青蜜月| 免费毛片一区二区三区久久久| 亚洲国产精品www| 欧美老女人xx| 亚洲中字黄色| 久久综合给合久久狠狠狠97色69| 亚洲国产精彩中文乱码av在线播放| 能在线观看的日韩av| 最近中文字幕mv在线一区二区三区四区| 亚洲三级影院| 欧美日韩中文另类| 欧美一级片一区| 亚洲国产精品成人综合色在线婷婷| 夜夜嗨av一区二区三区中文字幕| 国产精品日本欧美一区二区三区| 午夜电影亚洲| 欧美高清在线播放| 亚洲女女女同性video| 国产有码一区二区| 欧美jjzz| 欧美一级片久久久久久久 | 一区二区三区日韩欧美精品| 国产精品日日摸夜夜摸av| 久久人人超碰| 亚洲无限av看| 亚洲电影免费| 欧美一区二区三区免费看| 亚洲国产成人一区| 国产精品视频不卡| 欧美精品日韩| 久久精品国产亚洲一区二区| 日韩系列在线| 欧美国产一区二区| 久久久久久久网| 亚洲午夜激情| 亚洲精品乱码久久久久久久久 | 9色精品在线| 精久久久久久| 国产麻豆91精品| 欧美日韩www| 免费观看一级特黄欧美大片| 篠田优中文在线播放第一区| 日韩视频永久免费| 亚洲成人中文| 免费成人高清在线视频| 久久不射电影网| 午夜精品一区二区三区在线播放| 日韩亚洲欧美一区二区三区| 伊人成年综合电影网| 国产区日韩欧美| 国产精品欧美久久| 欧美午夜精品电影| 欧美日韩国产精品自在自线| 鲁大师成人一区二区三区| 久久精品国产91精品亚洲| 亚洲综合精品一区二区| 亚洲视频欧美视频| 一区二区三区免费观看| 亚洲经典视频在线观看| 欧美激情一区二区久久久| 美女被久久久| 欧美成人精品在线播放| 欧美成人中文| 欧美成人视屏| 亚洲国产另类久久久精品极度| 欧美成人自拍| 亚洲高清不卡| 亚洲国产免费| 99这里只有久久精品视频| 99精品欧美一区| 亚洲一区二区三区精品视频| 亚洲一线二线三线久久久| 午夜电影亚洲| 久久久91精品| 狂野欧美激情性xxxx欧美| 美女日韩在线中文字幕| 免费成人黄色| 欧美理论视频| 国产精品综合av一区二区国产馆| 国产视频精品xxxx| 国产在线视频欧美| 亚洲激情网站免费观看| 在线亚洲一区| 欧美一区=区| 欧美jizz19性欧美| 亚洲美女免费精品视频在线观看| 日韩一级欧洲| 久久经典综合| 欧美精品久久久久a| 国产精品高潮视频| 尤物九九久久国产精品的分类| 亚洲精品欧美专区| 午夜欧美大片免费观看| 麻豆成人在线播放| 亚洲理伦在线| 久久久久99| 欧美日韩视频不卡| 国产日韩视频| 99精品免费网| 久久综合中文色婷婷| 日韩视频精品在线观看| 欧美影院成人| 欧美日韩亚洲天堂| 在线观看福利一区| 亚洲免费视频成人| 欧美国产激情| 性欧美1819sex性高清| 欧美精品成人在线| 狠狠综合久久av一区二区小说| 99精品欧美一区二区三区综合在线| 欧美在线视频在线播放完整版免费观看 | 国产日韩在线播放| 亚洲作爱视频| 欧美电影美腿模特1979在线看 | 最近看过的日韩成人| 久久国产福利| 国产精品九九| 日韩一级视频免费观看在线| 久久精品人人做人人爽电影蜜月| 亚洲精品在线看| 美日韩精品视频免费看| 国产中文一区二区三区| 亚洲综合色在线| 亚洲精品美女久久久久| 久久一区二区三区国产精品|