#53292: DFS 思路提供
411435030@gms.ndhu.edu.tw
(呱呱嘎嘎)
學校
:
不指定學校
編號 : 317327
來源 : [134.208.58.9]
最後登入時間 ：
2025-09-03 23:44:04
思路:其實劃出圖形就會明白
首先，要先知道他說的<延遲時間>可以視為路徑長度
struct node
{
vector<int> from; // 前點
vector<int> to ; // 後點
int gate = -1; // -1 = 輸入 ,1 = and , 2 = or, 3 = xor, 4 = not
int output = -1; // 點的值
} ;
這樣可以處理掉前後順序的問題
vector<node> vec; //儲存所有節點
vector<int> dp; // 到這個節點的延遲
vector<int> dp; // 到這個節點的延遲
//輸入端
for(int i=0;i<p;i++)
{
cin >> vec[i].output;
}
//邏輯閘
for(int i=p;i<p+q;i++)
{
cin >> vec[i].gate;
}
// 前點 後點
for(int i=0;i<m;i++)
{
int a, b;
cin >> a >> b;
vec[b-1].from.push_back(a-1);
vec[a-1].to.push_back(b-1);
}
int maxDelay = 0;
for(int i=p;i<p+q;i++)
{
maxDelay = max(maxDelay, dfs(i));
}
cout << maxDelay -1 << endl;
// 輸出端
for (int i=p+q; i<p+q+r; i++)
{
cout << vec[vec[i].from[0]].output << " "; //這是找輸出端前面的邏輯閘運算後的值
}
著重說明輸出的時候是需要往前找的因為我的dfs只有計算邏輯閘，所以要找輸出端前面的邏輯閘運算後的值
這是主要的dfs函式
int dfs(int u) {
// DFS + 記憶化的邏輯可以在這裡寫
if (dp[u] != -1) return dp[u]; //避免重複算
int maxDelay = 0;
for(int pre:vec[u].from)//算延遲 (路徑長度
{
maxDelay = max(maxDelay, dfs(pre));
}
//確保所有from 都已接算好
if(vec[u].gate != -1)
{
if(vec[u].gate == 1) // and
{
vec[u].output = 1;
for(int pre: vec[u].from)
{
if(vec[pre].output == 0)
{
vec[u].output = 0;
break; // 一旦有0就可以停
}
}
}
else if(vec[u].gate == 2) // or
{
vec[u].output = 0;
for(int pre:vec[u].from)
{
if(vec[pre].output == 1)
{
vec[u].output = 1;
}
}
}
else if(vec[u].gate == 3) // xor
{
vec[u].output = 0;
for(int pre:vec[u].from)
{
vec[u].output ^= vec[pre].output;
}
}
else if(vec[u].gate == 4) //not
{
vec[u].output = vec[vec[u].from[0]].output == 0 ? 1 : 0;
}
}
dp[u] = maxDelay + 1; // 自己這層也要 +1 秒
return dp[u];
}