P5663 加工零件

2020 年 12 月 5 日
筆記
洛谷

設求第3點為第3階段時，點1是否需要提供原材料。

【3,3】 => 【2,2】，【4,2】

【2,2】 => 【1,1】，【3,1】
【4,2】 => 【3,1】，【5,1】

【1,1】 => 【2,0】，【5,0】
【3,1】 => 【2,0】，【4,0】
【5,1】 => 【1,0】，【4,0】 # 此處1需要提供原材料

比較容易想到對於每個詢問進行暴搜，若點1為0，則Yes
時間複雜度很高，必然超時。

40-60分算法

#include <bits/stdc++.h>
using namespace std;

const int MAXN=1005;
int vex[MAXN],k,n,m,q;
struct edge {
    int u,v,next;
}e[MAXN*2];

int vis[MAXN][MAXN];

void add(int u,int v){
    k++;
    e[k].u=u;
    e[k].v=v;
    e[k].next=vex[u];
    vex[u]=k;
}

void dfs(int u,int s){
    if(s==-1||vis[u][s]) return;
    vis[u][s]=1;
    for(int i=vex[u];i;i=e[i].next){
        int v=e[i].v;
        dfs(v,s-1);
    }
    return;
}

int main(){
    cin>>n>>m>>q;
    while(m--){
        int u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    while(q--){
        int u,L;
        memset(vis,0,sizeof(vis));
        cin>>u>>L;
        dfs(u,L);
        if(vis[1][0]) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

滿分算法

觀察發現，由於1->2的路徑長度為1，只要點2的階段為奇數，則點1一定要提供原材料（1->2->1->2->…)

觀察發現，由於1->2->3的路徑長度為2，只要點3的階段為偶數，則點1一定要提供原材料

從1到v，路徑很多，長度不盡相同。如果1到v的路徑長度存在4時，v在階段4、6、8、10…時，1肯定可以為0。當v的路徑長度存在3時，v在3、5、7、9…階段，1肯定可以為0。

因此要求的就是1到v的最短奇數路徑和最短偶數路徑。

若v的階段為偶數x，存在v的最短偶數路徑y，滿足x>=y，1即可為0。

若v的階段為奇數x，存在v的最短奇數路徑y，滿足x>=y，1即可為0。

設dis[v][0]為1到v的最短偶數路徑，設dis[v][1]為1到v的最短奇數路徑，

則有：

dis[v][0] = min(dis[v][0],dis[u][1]+1)
dis[v][1] = min(dis[v][1],dis[u][0]+1)

對於初始點1，dis[1][0]顯然等於0，dis[1][1]顯然不可能，設為無窮大。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int vex[MAXN],k,n,m,q;
struct edge {
    int u,v,next;
} e[MAXN*2];
int vis[MAXN][2],dis[MAXN][2],que[MAXN*10],q2[MAXN*10],head,rear;
void add(int u,int v) {
    k++;
    e[k].u=u;
    e[k].v=v;
    e[k].next=vex[u];
    vex[u]=k;
}
void SPFA() {
    for(int i=1; i<=n; i++) dis[i][0]=dis[i][1]=1e9;
    dis[1][0]=0;
    head=1;
    rear=0;
    que[++rear]=1;
    while(head<=rear) {
        int u=que[head];
        int t=q2[head];
        head++;
        vis[u][t]=0;
        for(int i=vex[u]; i; i=e[i].next) {
            int v=e[i].v;
            if(dis[v][0]>dis[u][1]+1) {
                dis[v][0]=dis[u][1]+1;
                if(!vis[v][0]) {
                    vis[v][0]=1;
                    que[++rear]=v;
                    q2[rear]=0;
                }
            }
            if(dis[v][1]>dis[u][0]+1) {
                dis[v][1]=dis[u][0]+1;
                if(!vis[v][1]) {
                    vis[v][1]=1;
                    que[++rear]=v;
                    q2[rear]=1;
                }
            }
        }
    }
    return;
}
int main() {
    freopen("work.in","r",stdin);
    freopen("work.out","w",stdout);
    cin>>n>>m>>q;
    while(m--) {
        int u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    SPFA();
    if(vex[1]==0) dis[1][0]=1e9; //補丁，若1點沒有連接邊，則1的偶數路徑沒有。
    
    while(q--) {
        int u,L;
        cin>>u>>L;
        if(L>=dis[u][L%2]) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

Tags: 洛谷