NOIP 2012 文化之旅题解

2024-04-03 10:23:22

来水一篇题解，我看洛谷上说的这道题的数据特别水，于是就写了很水的做法。

题目：P1078 [NOIP2012 普及组] 文化之旅 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目背景

本题是错题，后来被证明没有靠谱的多项式复杂度的做法。测试数据非常的水，各种玄学做法都可以通过（比如反着扫），不代表算法正确。因此本题题目和数据仅供参考。

题目描述

有一位使者要游历各国，他每到一个国家，都能学到一种文化，但他不愿意学习任何一种文化超过一次（即如果他学习了某种文化，则他就不能到达其他有这种文化的国家）。不同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同，有些文化会排斥外来文化（即如果他学习了某种文化，则他不能到达排斥这种文化的其他国家）。

现给定各个国家间的地理关系，各个国家的文化，每种文化对其他文化的看法，以及这位使者游历的起点和终点（在起点和终点也会学习当地的文化），国家间的道路距离，试求从起点到终点最少需走多少路。

输入格式

第一行为五个整数 N,K,M,S,TN,K,M,S,T，每两个整数之间用一个空格隔开，依次代表国家个数（国家编号为11到 NN），文化种数（文化编号为11到KK），道路的条数，以及起点和终点的编号（保证 SS 不等于TT）；

第二行为NN个整数，每两个整数之间用一个空格隔开，其中第 ii个数C_iCi，表示国家ii的文化为C_iCi。

接下来的 KK行，每行KK个整数，每两个整数之间用一个空格隔开，记第ii 行的第 j 个数为a_{ij}aij，a_{ij}= 1aij=1 表示文化 ii排斥外来文化jj（ii 等于jj时表示排斥相同文化的外来人），a_{ij}= 0aij=0 表示不排斥（注意ii 排斥 jj 并不保证jj一定也排斥ii）。

接下来的 MM 行，每行三个整数 u,v,du,v,d，每两个整数之间用一个空格隔开，表示国家 uu与国家 vv有一条距离为dd的可双向通行的道路（保证uu不等于 vv，两个国家之间可能有多条道路）。

输出格式

一个整数，表示使者从起点国家到达终点国家最少需要走的距离数（如果无解则输出-1−1）。

输入输出样例

输入 #1

输出 #1

-1

输入 #2

输出 #2

说明/提示

输入输出样例说明11

由于到国家 22 必须要经过国家11，而国家22的文明却排斥国家 11 的文明，所以不可能到达国家 22。

输入输出样例说明22

路线为11 ->22

【数据范围】

对于 100%的数据，有2≤N≤1002≤N≤100

1≤K≤1001≤K≤100

1≤M≤N^21≤M≤N2

1≤k_i≤K1≤ki≤K

1≤u, v≤N1≤u,v≤N

1≤d≤1000,S≠T,1≤S,T≤N1≤d≤1000,S=T,1≤S,T≤N

NOIP 2012 普及组第四题

题解：既然数据很水那么我们就来试试爆搜行不行吧：

思路：对于每个将要去到的节点判断一下前面有没有与他相矛盾的节点或者是已经去过的节点。

因为每条边的大小是大于1的显然走环的话答案肯定不是最小的。

没每经过一个节点就用一个栈来存进去，记得要回溯哟。

code：

#include <bits/stdc++.h>
using namespace std;
struct node {
    int f,t,val,nex;
}rt[10010];
int head[10010],cnt,vis[1010][1010],qaq[10010];
int be,ed,a,b,c,lo[10010];
int bec;
void add(int x,int y,int z) {
    cnt ++;
    rt[cnt].f = x;
    rt[cnt].t = y;
    rt[cnt].val = z;
    rt[cnt].nex = head[x];
    head[x] = cnt;
}
int sta[1010];
int ans = 0x3f3f3f3f;
void dfs(int x,int num,int co) {
    if(clock() - bec > 999900) {
        if(ans == 0x3f3f3f3f)
            cout<<-1;
        else
            cout<<ans;
        exit(0);
    }
    if(x == ed){
        ans = min(ans,co);
    }
    else {
        for(int i = head[x];i;i = rt[i].nex) {
            bool faq = 1;
            for(int j = 1;j <= num;j ++) {
                if(qaq[rt[i].t])
                    faq = 0;
                if(vis[lo[rt[i].t]][lo[sta[j]]] || lo[rt[i].t] == lo[sta[j]])
                    faq = 0;
            }
            if(faq) {
                qaq[rt[i].t] = 1;
                sta[num + 1] = rt[i].t;
                dfs(rt[i].t,num + 1,co + rt[i].val);
                qaq[rt[i].t] = 0;
            }
        }
    }
}
int main() {
    bec = clock();
    cin>>a>>c>>b>>be>>ed;
    for(int i = 1;i <= a;i ++) {
        cin>>lo[i];
    }
    int x,y;
    for(int i = 1;i <= c;i ++) {
        for(int j = 1;j <= c;j ++) {
            cin>>x;
            vis[i][j] = x;
        }
    }
    int z;
    for(int i = 1;i <= b;i ++) {
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
    }
    qaq[be] = 1;
    sta[1] = be;
    dfs(be,1,0);
    if(ans == 0x3f3f3f3f)
        cout<<-1;
    else
        cout<<ans;
    return 0;
}
/*
10 5 18 1 7
4 2 5 3 2 2 1 2 3 2
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 2 656
2 4 989
2 1 947
3 2 731
4 10 830
4 8 688
5 6 573
5 3 492
6 10 700
6 3 854
8 7 839
8 7 461
10 9 885
10 9 960
4 7 4
3 4 8
2 3 4
1 2 5

 */

由于爆搜的话复杂度肯定过不去，所以在要超时的时候就可以输出了反正数据很水。[doge][doge][doge].

码农公寓