2024.10.12 鮮花
雙極定向
INTERNET YAMERO
インターネット?エンジェルという現(xiàn)象は
當(dāng)代互聯(lián)網(wǎng)小天使這種現(xiàn)象
仮定された有機(jī)交流電燈の
是被假定為有機(jī)交流電燈的
かわいい虹色の照明です ぶいっ
一盞可愛虹色照明 耶
あらゆる透明なアカウントの複合體
(所有透明賬號的復(fù)合體)
このクソゴミカスキショキショな現(xiàn)実を
忘記傻逼垃圾智障的現(xiàn)實吧
忘れさせてあげる 慈愛の天使
幫助你的我乃是 慈愛天使
大人のみんなにはナイショだぞ
這件事可不能告訴大人們哦
大丈夫もうなにも怖くないから
沒事的什么都不用怕了
こんなSNS抜けだして二人で海を見に行くぞ!
這破爛SNS待不下去 我們逃走去看海吧!
インターネットや?め?ろ~!!!
因特網(wǎng)呀 快·遠(yuǎn)·離~!!!
わかる真似をして なにも知らないね アナタ
自以為「我可以懂你」 實際上一無所知的 網(wǎng)友呀
なにが悲しいの なにが寂しいの 聴こえてる?
究竟在悲傷什么 究竟在寂寞什么 你聽見了嗎?
人が戀しくて 人がイヤすぎて ループ
既貪戀人們的溫暖 又厭惡人們的麻煩 循環(huán)
夜が好きなのに 一人じゃ寒くて 震えてる
明明就很喜歡夜晚 獨自一人卻覺苦寒 抖顫
ほんとうは幸せを知っているのに
其實我很清楚幸福的樣子是什么
不幸なフリやめられないね
卻無法停止 假裝世界欠我的
アンチに負(fù)けず 信者に媚びず
不輸黑子 不媚信徒
どんなに努力を重ねても
小小天使不論怎樣努力
一寸先は地獄行き
一步之差便往地獄直行
いやもうすでに冥府魔道
其實早已踏上冥府魔道
地獄の沙汰もいいね次第
有道是高贊能使鬼推磨
偽善者トラップ蜘蛛の糸
偽善者的陷阱蜘蛛之絲
こんなに苦しい筈なのに
明明是如此痛苦室息
インターネットがやめられないない!
卻根本無法從因特網(wǎng)遠(yuǎn)離遠(yuǎn)離!
発狂!
發(fā)狂!
かけめぐるエクスタシー 融けるマイスリー
游走全身的 Ecstasy 漸漸消融的 Myslee
畫面光りだすの 不安止まらないよ
屏幕開始閃爍 心中止不住擔(dān)憂
誰か殺してくれ イヤだ死にたくない
誰快來殺了我吧 不要啊我不想死
朝は見たくないの
不想見到早晨來臨
ムリだ!死ぬ!頭が割れてく!!!!!1
不行了!要 命!腦袋要裂開啦!!!!!1
いやー! 死んいたい! 死ぬ! いやー やめろ!
(呀一—!!!好想死哦!!!!要死啦!!!不要!!!住手呀!!!)
それでもわたしはこのカオスをオタクと歩む
即便如此我仍會與宅宅一同在混沌中前行
ここにしかない光景を見つけに行くから
我們要去尋找只有在這里能見到的光景
あんなにおそろしい亂れたインターネットから
從那可怖的狂亂的因特網(wǎng)中降下的
この雪みたいに美しい毒電波がきたんだよ
這些 毒電波竟然如雪一般美麗
カウンセリングを受けたの
我去做心理咨詢了哦
先生から「ネットをやめろ」って言われて
醫(yī)生讓我「不要再上網(wǎng)了」
もうおまえらと會えないと思った瞬間 胸が苦しくて
一想到再也見不到你們的瞬間 心里好難過
リアルが壊れてもココが良いって思ったの
哪怕現(xiàn)實會分崩離析 我也更喜歡這里啊
初めてフォローされた日のこと覚えてる
我還記得第一次被人關(guān)注的那天
こんなわたしを見て?承認(rèn)してくれたヌクモリティ
看見我 認(rèn)可我 人間溫暖我的心
もう細(xì)かいことはどうでもいいね せーのっ
也用不著在意什么細(xì)節(jié)了 來一起喊
インターネット最高!!!
當(dāng) 代 互 聯(lián) 網(wǎng) 天·下·第·一!!!
ほとばしるエクスタシー 甘い夢をみせてマイスリー
洶涌迸發(fā)的 Ecstasy 讓我做個好夢吧 Myslee
指先で感じる 泳ぐ電子の海 インターネット?ボーイ
用指尖去細(xì)細(xì)感觸 電子之海中暢游的 Internet Boy
悲しみ舞い散る 暗い闇の中インターネット?ゲーム
悲傷憂郁四散飛舞 黑暗之中的 Internet Game
アナタのとなり微笑む 忘れないでいてねインターネット?ガール
在你身旁微笑展露 要一直記住我哦 Internet Girl
きっと……
一定會……
キボンヌ!オワタ!半年ROMれ!
(球球了!)(完蛋了!)(潛水半年再來罷!)
??――(???)――! age!漏れ!香具師(やし)!
(??――(???)――!)(ddd!)(本弟弟!)(鐵汁們!)
逝ってよし!久々にワロタ!
(去世罷!)(笑死!)
ぽまいら!
(你們啊!)
これは 乙じゃなくて ポニーテールなんだからね!
(才不是為了犒勞你,只是扎個馬尾而已!)
ブヒヒ!ぬるぽ!禿同!
(咕嘿嘿!)(錕斤銬!)(怒贊!)
キボンヌ! 無理ぽ!
(球球了!) (感覺8行!)
オワタ! オマエモナー!
(完蛋了!) (寧不也是!)
半年ROMれ! お禮は3行!
(潛水半年再來罷!) (字?jǐn)?shù)不夠彩虹屁!)
??――(???)――! うp汁!
(kita――(???)――!) (鏈接呢!)
age!漏れ! 日本語でおk!
(ddd!)(本弟弟!) (說人話!)
香具師!逝ってよし! >>1の母です!
(鐵汁們!)(去世罷!) (我是樓主的爸爸!)
久々にワロタ!
(笑死!)
キボンヌ!オワタ!半年ROMれ!
(球球了!)(完蛋了!)(潛水半年再來罷!)
??――(???)――! age!漏れ!
(kita――(???)――!)(ddd!)(本弟弟!)
香具師!逝ってよし!
(鐵汁們!)(去世罷!)
禿同!
(怒贊!)
好き 好き 好き 好き 好き 好き 好き 好き
好き 好き 好き 好き 好き 好き 好き 好き
喜歡 喜歡 喜歡 喜歡 喜歡 喜歡 喜歡 喜歡
喜歡 喜歡 喜歡 喜歡 喜歡 喜歡 喜歡 喜歡
青白いモニター越しの光を通し
以隔著冷色屏幕投下的光芒
オタクの孤獨を癒やして回る
四處治愈宅宅們的孤獨
わたしはインターネットの天使なのだ
我就是 互聯(lián)網(wǎng)上的 天使啊

我竟然真的有一天可以賀到歌詞
吉吉定向
問題:給定一張無向連通圖 G 和點 S,T,要求對每條邊定向,使得 G 成為一張 DAG,且有且僅有 S 入度為零,有且僅有 T 出度為零。
耳:若對于 \(G=(V,E)\) 的子圖 \(G'=(V',E')\) 存在 \(x_1,x_2,\cdots,x_k\),滿足 \(x_1, x_k\in V', x_2, \cdots, x_{k - 1}\notin V'\) 且 \(\forall i > 1, (x_{i - 1}, x_i)\in E\),則稱頂點序列 \(x\) 是 \(G'\) 的耳 . 特別的,當(dāng) \(x_1\not=x_k\) 時,稱這個耳為開耳。
耳分解:若圖 \(G\) 的一個子圖序列 \(G_0,G_1,\cdots,G_k\) 滿足 \(G_0\) 僅存在一個點或兩個點及兩點之間的一條邊,\(G_k = G, \forall i > 0, G_{i - 1}\subsetneqq G_{i}\) 且 \(G_{i}\setminus G_{i - 1}\) 是 \(G_{i?1}\) 的一個耳,則稱該子圖序列為 \(G\) 的一個耳分解 . 特別的,若所有 \(G_{i}\setminus G_{i - 1}\) 都是 \(G_{i?1}\) 的開耳,則稱該耳分解為開耳分解 .
有結(jié)論:
- \(G\) 是邊雙 \(\iff G\) 存在耳分解。
- \(G\) 是點雙 \(\iff G\) 存在開耳分解。
考慮一個圖有雙極定向,當(dāng)且僅當(dāng)加入邊 \((S,T)\) 后是點雙,即存在開耳分解。
必要性是顯然的,考慮加入邊 \((S,T)\) 后是點雙等價于是一個點或縮點后是一條鏈且 \(S,T\) 分別是其端點,顯然縮點后除了 \(S\rightsquigarrow T\) 以外的點一定沒法走到。
我們假裝存在 \((S,T)\) 這條邊,其實是沒關(guān)系的,他的作用只是確定初始耳的定向,然后依次加耳即可。
建議看代碼理解實現(xiàn),實現(xiàn)的細(xì)節(jié)挺多的。
K8 的寫法是寫 tarjan 判無解,但其實直接判斷所有邊是否都定向了即可。
考慮每個邊被恰好定向一次,復(fù)雜度 \(O(n+m)\)
Code
#include<bits/stdc++.h>
using namespace std;
using llt=long long;
using llf=long double;
using ull=unsigned long long;
#define endl '\n'
#ifdef LOCAL
FILE *InFile=freopen("in_out/in.in","r",stdin),*OutFile=freopen("in_out/out.out","w",stdout);
#else
FILE *InFile=stdin,*OutFile=stdout;
#endif
const int N=4e5+3,M=1e6+3;
int n,m;
struct Gph{
int hd[N],to[M<<1],nt[M<<1],tot=1;
void Add(int u,int v){to[++tot]=v,nt[tot]=hd[u],hd[u]=tot;}
void ADD(int u,int v){Add(u,v),Add(v,u);}
void Clr(){for(int i=1;i<=n;++i) hd[i]=0; tot=1;}
#define For_to(i,u,v,g) for(int i=g.hd[u],v=g.to[i];i;i=g.nt[i],v=g.to[i])
}g;
class JJD{ // 是 JJ 定向,不是 JJ 大王
private:
bool vis[M]; int stk[N],dep[N],fa[N],fe[N];
vector<pair<int,int>> off[N]; queue<pair<int,int>> dfq;
void Dfs(int u,int d){
stk[dep[u]=d]=u; // 當(dāng)前鏈
For_to(i,u,v,g){ // 預(yù)處理
int id=i>>1;
if(id==fe[u]) continue;
if(!dep[v]) cu[id]=u,cv[id]=v,fa[v]=u,fe[v]=id,Dfs(v,d+1);
else if(dep[u]>dep[v]) cu[id]=v,cv[id]=u,off[stk[dep[v]+1]].emplace_back(u,id);
}
}
void Def(int u,int d){ // 定向
if(vis[fe[u]]||u==s) return ;
vis[fe[u]]=1; if(d) swap(cu[fe[u]],cv[fe[u]]);
for(auto k:off[u]){
int v=k.first,id=k.second;
dfq.emplace(v,d^1);
vis[id]=1; if(d) swap(cu[id],cv[id]);
}
Def(fa[u],d);
}
public:
int s,t,cu[M],cv[M];
void In(){Dfs(s,1);}
bool operator()(){
dfq.emplace(t,0); while(!dfq.empty()){auto k=dfq.front(); dfq.pop(); Def(k.first,k.second);}
for(int i=1;i<=m;++i) if(!vis[i]) return 0; return 1;
}
void Out(){for(int i=1;i<=m;++i) cout<<cu[i]<<' '<<cv[i]<<endl;}
void Clr(){for(int i=1;i<=n;++i) dep[i]=fa[i]=fe[i]=0,vector<pair<int,int>>().swap(off[i]); for(int i=1;i<=m;++i) vis[i]=0;}
}Jjd;
void Clr(){g.Clr(),Jjd.Clr();}
void Slv(){
cin>>n>>m>>Jjd.s>>Jjd.t; for(int i=1;i<=m;++i) cin>>Jjd.cu[i]>>Jjd.cv[i],g.ADD(Jjd.cu[i],Jjd.cv[i]);
Jjd.In();
if(!Jjd()) cout<<"No"<<endl;
else cout<<"Yes"<<endl,Jjd.Out();
}
int main(){
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int t; cin>>t; while(t--) Slv(),Clr();
}
P

本文來自博客園,作者:xrlong,轉(zhuǎn)載請注明原文鏈接:http://www.rzrgm.cn/xrlong/p/18461333
版權(quán)聲明:本作品采用 「署名-非商業(yè)性使用-相同方式共享 4.0 國際」許可協(xié)議(CC BY-NC-SA 4.0) 進(jìn)行許可。

浙公網(wǎng)安備 33010602011771號