---
# System prepended metadata

title: APCS 高級 202603 骨牌堆疊

---

# APCS 高級 202603 骨牌堆疊

已知圖中只有可能形成環跟鍊
首先我將邊權轉為點權(我覺得這樣好做，看個人喜好)
再來分別用head、tail兩個陣列將每個點對應並串接起來
再來鍊和環分開處理
(要一起處理也是可以，程式碼會比較乾淨，但是分開寫看起來會比較清楚)

鍊的區間最大和處理大家應該都會
但是環就會分為下列兩種情形
假設將環拆成鍊來看
綠色為採用的骨牌區間


---
情況一:
![123](https://hackmd.io/_uploads/S19rXpocWe.png)
---
情況二:
![1234](https://hackmd.io/_uploads/BJll4Toqbe.png)
---
## 以下為程式碼實作:

```cpp=
#include<bits/stdc++.h>
#define ll long long

using namespace std;

vector<bool> visited;
vector<ll> val;
vector<vector<int>> v;

ll ans = -1e18;

void run_chain(int x){
    ll cur_sum = 0;
    while(!visited[x]){
        cur_sum += val[x];
        visited[x] = true;
        ans = max(ans, cur_sum);
        if(cur_sum <= 0) cur_sum = 0;
        if(!v[x].empty()) x = v[x][0];
    }
    return;
}

void run_cycle(int x){
    ll cur_sum = 0;
    ll pre_max = 0;
    ll pre_min = 0;
    ll cur_min = 1e18;
    while(visited[x] == false){
        cur_sum += val[x];
        visited[x] = true;
        pre_max = max(pre_max + val[x], val[x]);
        pre_min = min(pre_min + val[x], val[x]);
        cur_min = min(cur_min, pre_min);
        ans = max(pre_max, ans);
        if(!v[x].empty())x = v[x][0];
    }
    ans = max(cur_sum - cur_min, ans);
    return;
}

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

    int n,m; cin >> n >> m;
    vector<int> head(n+1, 0);
    vector<int> tail(n+1, 0);
    vector<bool> no_parent(n+1, 1);
    visited.resize(n+1); v.resize(n+1); val.resize(n+1);
    for(int i = 1,a,b; i<=m;i++){
        cin >> a >> b;
        cin >> val[i];
        head[a] = i;
        tail[b] = i;
        if(head[b] != 0){
            v[i].push_back(head[b]);
            no_parent[head[b]] = false;
        }
        if(tail[a] != 0){
            v[tail[a]].push_back(i);
            no_parent[i] = false;
        }
    }
    
    for(int i  = 1; i<=m; i++){
        if(no_parent[i] == true){
            run_chain(i);
        }
    }
    for(int i  = 1; i<=m; i++){
        if(visited[i] == false){
            run_cycle(i);
        }
    }
    cout << ans << "\n";
}
```