今天我們來看看CF228E 題目連結
題目描述
給定一個包含 $n$ 個城市和 $m$ 條道路的無向圖，每條道路都有一個初始狀態：
- 0 表示該道路尚未鋪設；
- 1 表示該道路已鋪設。
每天，國王 Valera II 可以選擇 恰好一個城市，並指派工人對該城市相連的所有道路進行取反操作（即將 0 變為 1，1 變為 0）。
由於對同一城市重複操作沒有額外效果（取反兩次恢復原狀），所以每個城市最多只需操作一次。
你的任務是判斷是否存在一個操作序列（操作天數不超過 $n$ 天），使得最終所有道路均變為鋪設狀態（即狀態均為 1）。若存在，請輸出一組合法的操作方案；否則，輸出 Impossible。
輸入格式
- 第一行包含兩個整數 $n$ 和 $m$，分別代表城市數量和道路數量。
- 接下來 $m$ 行，每行包含三個整數 $a_i, b_i, c_i$：
- $a_i$ 和 $b_i$ 表示一條連接這兩個城市的道路（保證 $a_i \neq b_i$）；
- $c_i$ 為該道路的初始狀態（$0$ 表示未鋪設，$1$ 表示已鋪設）。
輸出格式
- 如果存在合法操作序列：
- 第一行輸出操作天數 $x$（滿足 $0 \le x \le n$）；
- 第二行輸出 $x$ 個整數，依次表示每天選擇操作的城市編號。
- 如果不存在合法方案，則輸出
Impossible。
前言
想不出來的時候還是多看解答好了，以免浪費時間在我沒學過的演算法上面
想法
這題看起來有三種解法：
- 高斯消去法
- 2-SAT
- Greedy
這次我使用第二種，2-SAT的方法。剛好把以前沒學懂的BCC、SCC、DFS回邊、前向邊、樹邊、交錯邊學起來。
這題對我來說就是2-SAT的模板題：
開一張新的圖，如果原圖中$x,y$的連線是$0$，那麼邏輯關係就是:
\begin{align*}
&x\rightarrow\neg y \
&\neg x\rightarrow y \
&\neg y\rightarrow x \
&y\rightarrow\neg x
\end{align*}
反之如果原圖中$x,y$的連線是$1$，那麼邏輯關係就是:
\begin{align*}
&x\rightarrow y \
&\neg x\rightarrow\neg y \
&\neg y\rightarrow\neg x \
&y\rightarrow x
\end{align*}
而我們新的圖裡面可以用$x*2$當成False的點，$x*2+1$當成True的點，用這個規則造一張新的，包含$2n$個節點的新圖。
接著使用Tarjan’s Algorithm找SCC。
Tarjan找BCC和找SCC除了無向圖和有向圖的差異以外，就在
if (!scc[u]) low[v] = min(low[v], low[u]);
這一行而已。
如果要找BCC，我們的dfs函數就需要有int father這個參數，判斷接下來要dfs的點是不是父節點(有向圖裡面往父節點的邊也是合理的回邊)。並且由於無向圖沒有交錯邊，因此不需要判斷!scc[u]
注意到Tarjan SCC裡面，我們指派SCC Number是在dfs的後序的地方。而回憶起拓樸排序的其中一種作法就是紀錄dfs的後序，就是反過來的拓樸順序了。
而SCC縮點以後，會是一個有向無環圖(DAG)，因此SCC Number小的SCC，會在拓樸排序的後面。
當然，我們要先確認有沒有邏輯矛盾，也就是會不會有$x\rightarrow\neg x$的情況發生，也就是$x$和$\neg x$的節點在圖的同一個SCC中。
再來我們就可以從後面開始指派布林變數的值了。因為如果我們從後面開始指派，就不會有邏輯關係可以卡到我們了，例如，$x\rightarrow y$在SCC Number=2的SCC中，而$\neg x\rightarrow\neg y$在SCC Number=1的SCC中。
如果我們先指定$y=true$，因為SCC=2會有邏輯關係指向SCC=1，因此就會發生$y\rightarrow…\rightarrow\neg x\rightarrow\neg y$，發生矛盾。
因此我們必須指定$\neg y=true$，也就是$y=false$。如此一來前面的
$$
y\rightarrow…\rightarrow\neg x\rightarrow\neg y
$$
就會因為前提$y$根本不成立，而不會有矛盾。
(這個說明方法我也不是那麼確定是不是對的，如果有人知道正確的講法，還請賜教)
程式碼:
const int _n = 100 + 10;
int t, n, m, T = 0;
VI G[_n * 2];
int id[_n * 2], low[_n * 2], scc[_n * 2];
stack<int> st;
void dfs(int v) { // Tarjan SCC
id[v] = low[v] = ++T; // 前序
st.push(v);
for (int u : G[v]) {
if (!id[u]) dfs(u);
if (!scc[u]) low[v] = min(low[v], low[u]); // 如果是要求BCC 就要判斷u!=father 然後不用判斷!scc[u]
}
if (low[v] == id[v]) {
int temp;
do {
scc[temp = st.top()] = v; // SCC是dfs的後序，剛好是縮點後的DAG的拓樸排序
st.pop();
} while (temp != v);
}
}
main(void) {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
rep(i, 0, m) {
int a, b, c;
cin >> a >> b >> c;
a--, b--; // 這跟題目有關 題目的vertex是1-indexed
if (c) {
G[a * 2 + 1].pb(b * 2 + 1); // x*2 false, x*2+1 true
G[b * 2 + 1].pb(a * 2 + 1);
G[a * 2].pb(b * 2);
G[b * 2].pb(a * 2);
} else {
G[a * 2 + 1].pb(b * 2);
G[b * 2 + 1].pb(a * 2);
G[b * 2].pb(a * 2 + 1);
G[a * 2].pb(b * 2 + 1);
}
}
rep(i, 0, n) {
if (!id[i * 2]) dfs(i * 2);
if (!id[i * 2 + 1]) dfs(i * 2 + 1);
}
// tarjan 算出來的scc 實際上是反過來的topo order
// 而這剛好是我們找2-SAT最後的解要的：反過來的topo order
// 檢查同個scc裡面有沒有 p and ~p，如果有，有矛盾，不可能
rep(i, 0, n) {
if (scc[i * 2] == scc[i * 2 + 1]) {
cout << "Impossible\n";
return 0;
}
}
VI ans;
rep(i, 0, n) {
// scc比較小的 出現在拓樸排序的比較後面
if (scc[i * 2 + 1] < scc[i * 2]) {
ans.pb(i + 1); // 這跟題目有關 題目的vertex是1-indexed
}
}
cout << ans.size() << '\n';
for (int x : ans) {
cout << x << ' ';
}
cout << '\n';
return 0;
}
標頭、模板請點Submission看 Submission