月份: 2021 年 4 月

台中女中-109-6 超級大轉機

mtmatt競賽題Leave a Comment on 台中女中-109-6 超級大轉機

用到了 Bellman-Ford Shortist Path Algorithm

#include<iostream>
using namespace std;
#define INF 1e9

struct edge{
    int from,to,cost;
};

int d[505],c[505],n,m;
edge a[10050];

void shortistPath(){
    while(1){
        bool update=false;
        for(int i=0;i<2*m;i++){
            if(d[a[i].from]!=INF && 
              d[a[i].to]>d[a[i].from]+a[i].cost+c[a[i].to]){
                d[a[i].to]=d[a[i].from]+a[i].cost+c[a[i].to];
                update=true;
            }
        }
        if(!update) break;
    }
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>c[i];
        d[i]=INF;
    }
    cin>>m;
    for(int i=0;i<m;i++){
        cin>>a[i].from>>a[i].to>>a[i].cost;
        a[m+i].from=a[i].to;
        a[m+i].to=a[i].from;
        a[m+i].cost=a[i].cost;
    }
    d[1]=0;
    shortistPath();
    if(d[n]!=INF){
        cout<<d[n];
    }else{
        cout<<"-1";
    }
    return 0;
}

C++ APCS實作題 2020/1 4 : 貨物分配

mtmattAPCS, APCS實作題Leave a Comment on C++ APCS實作題 2020/1 4 : 貨物分配

關於樹狀圖的應用

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

int w[2000010]={0},st[10010],child[2000010][2],n,m;

int dfs(int a){
    if(a>=n) return w[a];
    w[a]=dfs(child[a][0])+dfs(child[a][1]);
    return w[a];
}

int findBox(int stw,int a){
    if(a>=n){
        return a;
    }
    if(w[child[a][0]]<=w[child[a][1]]){
        w[child[a][0]]+=stw;
        return findBox(stw,child[a][0]);
    }
    w[child[a][1]]+=stw;
    return findBox(stw,child[a][1]);
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>w[n+i];
    
    for(int i=0;i<m;i++) cin>>st[i];
    
    for(int i=1;i<n;i++){
        int p,s,t;cin>>p>>s>>t;
        child[p][0]=s;child[p][1]=t;
    }
    int root=1;
    w[1]=dfs(root);
    for(int i=0;i<m;i++){
        cout<<findBox(st[i],root)<<" ";
    } 
    
    return 0;
}

C++ APCS實作題 2017/10 3 : 樹狀圖分析

mtmattAPCS, APCS實作題Leave a Comment on C++ APCS實作題 2017/10 3 : 樹狀圖分析

樹狀圖的結構以及 DFS ( 深度優先搜索 ) ，另外用了 height[] 來儲存高度以降低複雜度。

#include<bits/stdc++.h>
using namespace std;
#define For(i,a,b) for(int i=(a);i<(b);i++)

long long n;
vector<long long> child[100010];
long long p[100010],height[100010];

void dfs(long long a){
    height[a]=0;
    for(long long v:child[a]){
        dfs(v);
        height[a]=max(height[a],height[v]+1);
    }
    return;
}

int main(){
    cin>>n;
    For(i,1,n+1){
        long long chN;cin>>chN;
        For(j,0,chN){
            long long ch;cin>>ch;
            child[i].push_back(ch);
            p[ch]=i;
        }
    }
    int root;
    for(root=1;root<=n;root++){
        if(p[root]==0) break;
    }
    dfs(root);
    long long total=0;
    for(int i=1;i<=n;i++) total+=height[i];
    cout<<root<<"\n";
    cout<<total<<"\n";
    return 0;
}