ural 1651 Shortest Subchain

ゞ浴缸里的玫瑰 2021-12-14 12:43 120阅读 0赞

http://acm.timus.ru/problem.aspx?space=1&num=1651

这是今天训练的题，最近的训练都没有暑假的时候这么好的状态。整场训练，实际上有好几题可以做的，可是一开始就遇见这题，然后开始的时候做的方法不对，所以一直卡在这题，直到最后一个小时才出那两道水题。开始的时候以为这题就一个简单的bfs，直到打完比赛才明白原来这题是最短路。图论的题我都不太擅长，所以今天就这样卡死了。。。囧！

这题构图用的方法是先建好原路径的边，每个位置是一个点，然后标号相同的临近两个位置连一条长度是0的边，然后一个spfa搜索到结尾，最后回溯一下就可以得到目标序列了。

代码如下：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <cstdio>
      2 #include <cstring>
      3 #include <algorithm>
      4 #include <vector>
      5 
      6 using namespace std;
      7 
      8 const int maxn = 100005;
      9 const int inf = 0x7f7f7f7f;
     10 typedef pair<int, int> pii;
     11 typedef vector<pii> vpii;
     12 int rec[maxn], dis[maxn], buf[maxn];
     13 bool inq[maxn];
     14 vpii rel[maxn], opRel[maxn];
     15 
     16 void input(int n) {
     17     for (int i = 0; i < maxn; i++) {
     18         rec[i] = -1;
     19         rel[i].clear();
     20         opRel[i].clear();
     21         dis[i] = inf;
     22         inq[i] = false;
     23     }
     24 
     25     int cur;
     26 
     27     scanf("%d", &cur);
     28     rec[cur] = 0;
     29     buf[0] = cur;
     30     for (int i = 1; i < n; i++) {
     31         scanf("%d", &cur);
     32         buf[i] = cur;
     33         rel[i - 1].push_back(make_pair(i, 1));
     34         opRel[i].push_back(make_pair(i - 1, 1));
     35         if (~rec[cur]) {
     36             rel[rec[cur]].push_back(make_pair(i, 0));
     37             opRel[i].push_back(make_pair(rec[cur], 0));
     38         }
     39         rec[cur] = i;
     40     }
     41 
     42 //    for (int i = 0; i < n; i++) {
     43 //        printf("%d :", i);
     44 //        for (int j = 0, size = rel[i].size(); j < size; j++) {
     45 //            printf(" %d-%d", rel[i][j].first, rel[i][j].second);
     46 //        }
     47 //        puts(" ~~");
     48 //    }
     49 }
     50 
     51 int q[maxn], qh, qt;
     52 
     53 void spfa(int s) {
     54     int cur = s;
     55 
     56     qh = qt = 0;
     57     q[qt++] = s;
     58     dis[s] = 0;
     59     inq[cur] = true;
     60     while (qh < qt) {
     61         cur = q[qh++];
     62         inq[cur] = false;
     63 
     64         for (vpii::iterator ii = rel[cur].begin(); ii != rel[cur].end(); ii++) {
     65             int next = (*ii).first, len = (*ii).second;
     66 
     67             if (dis[next] > dis[cur] + len) {
     68                 dis[next] = dis[cur] + len;
     69                 if (!inq[next]) {
     70                     q[qt++] = next;
     71                     inq[next] = true;
     72                 }
     73             }
     74         }
     75     }
     76 //    for (int i = 0; i < 10; i++) {
     77 //        printf("dis %d : %d\n", i, dis[i]);
     78 //    }
     79 }
     80 
     81 int Stack[maxn], top;
     82 
     83 void backTrack(int T) {
     84     top = -1;
     85 
     86     int cur = T;
     87 
     88     Stack[++top] = buf[cur];
     89     while (cur) {
     90         for (vpii::iterator ii = opRel[cur].begin(); ii != opRel[cur].end(); ii++) {
     91             if (dis[cur] == dis[(*ii).first] + (*ii).second) {
     92                 cur = (*ii).first;
     93                 if (Stack[top] != buf[cur]) Stack[++top] = buf[cur];
     94                 break;
     95             }
     96         }
     97     }
     98     while (~top) {
     99         printf("%d", Stack[top]);
    100         if (top) {
    101             putchar(' ');
    102         }
    103         top--;
    104     }
    105     puts("");
    106 }
    107 
    108 int main() {
    109     int n;
    110 
    111 //    freopen("in", "r", stdin);
    112     while (~scanf("%d", &n)) {
    113         input(n);
    114         spfa(0);
    115         backTrack(n - 1);
    116     }
    117 
    118     return 0;
    119 }

——written by Lyon

转载于:https://www.cnblogs.com/LyonLys/archive/2012/10/30/Ural\_1651\_Lyon.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211214/3b2a6f53c5a0445aa93f0282138497ef.png