UPD 2020.04.30：本題解被發現存在嚴重錯誤，已更正。

題目鏈接

https://codeforces.com/contest/1338/problem/E

題解

這題太神了……這才是 div1E 啊，比什么 nim 積意義下的離散對數之類的高明到不知道哪里去了
這篇題解主要復述一下官方題解并補充一下官方題解上省略的證明。所有證明都是蒟蒻口胡的，有問題敬請指出。

下面把題目保證不存在的那個 $4$ 個點的子圖稱作 $H$，用四元組表示 $H$ 時，默認最后一個點入度為 $3$；整張圖的點集記作 $V$. 設一個點 $u$ 的入點集合為 $in(u)$.

首先對這個圖進行拓撲排序，每次刪掉入度為 $0$ 的點，則該點對答案的貢獻是 $(614n+1)$ 乘以剩下的點數。不妨假設剩下的圖非空，下面的內容都在剩下的圖上進行。我們會發現：
引理 0 不存在入度為 $0$ 的點時，整張圖是強連通的。
證明 對其縮點后，大小超過 $1$ 的 SCC 必定有三元環，而入度為 $0$ 的 SCC 必定大小超過 $1$. 因此如果 SCC 個數超過 $1$，則取入度為 $0$ 的 SCC 的一個三元環和其余的 SCC 中的一個點，會構成 $H$.
引理 1 $?u,in(u)\cup \{u\}$ 無環。
證明 反證，如果有環的話環上的點構成一個大小至少為 $3$ 的 SCC，必定存在三元環，和 $u$ 點構成 $H$.
引理 2 任取一個點 $X$，我們可以把整張圖劃分為兩部分 $P=in(X)\cup \{X\},Q=V?P$，則存在 $u\in Q,v\in P$ 滿足 $(u,v)$ 有邊。
證明 由于整張圖強連通，顯然。
（題解在這里的做法是取度數最大的點作為 $X$，實際上是需要的，理由將在下面給出。）
任取一個滿足引理 2 條件的點 $v$. 設 $R=in(v)\cap Q,S=Q?R$.
引理 3 $?y\in S,z\in R$，$(y,z)$ 有邊。
證明 反證，設 $(z,y)$ 有邊，則 $(v,X,z,y)$ 四個點構成 $H$.
引理 4 $S$ 無環，$R$ 無環。
證明 根據引理 1 得 $R$ 無環；若 $S$ 有環則和 $R$ 中任何一點構成 $H$.
引理 5 $P$ 無環，$Q$ 無環。
證明 根據引理 1 得 $P$ 無環，由 $S,R$ 分別無環且 $S,R$ 之間連的邊都由 $S$ 指向 $R$ 得到 $Q=S\cup R$ 無環。
到這里，我們就知道我們把這張圖劃分成了兩個部分，且兩部分分別無環。

對兩部分分別進行拓撲排序，并給他們標號為 $P_i,Q_i$（現在把集合看成序列），不妨設 $i<j$ 當且僅當存在邊 $(P_i,P_j)$，$Q$ 同理。
設 $inP(u)=in(u)\cap P,inQ(u)=in(u)\cap Q$.
引理 6a $?i$，$inQ(P_i)$ 為 $Q$ 的一段后綴；
證明 反證，若存在 $j<k$ 滿足 $(P_i,Q_k),(Q_j,P_i)$. 注意到 $P$ 的最后一個元素是 $X$，且 $X$ 向 $Q$ 中每個點都連了邊。于是 $(P_i,Q_j,X,Q_k)$ 構成 $H$.
那么不難發現，$?i,j$, 若$|inQ(P_i)|=|inQ(P_j)|$ 則 $inQ(P_i)=inQ(P_j)$，否則大的包含小的。
引理 6b $?i$，$inP(Q_i)$ 為 $P$ 的一段后綴。
證明 設 $l_i$ 為最小的 $j$ 滿足 $(Q_j,P_i)$ 有邊（若不存在視為 $+\infty$），可以證明 $l_i\le l_{i+1}$.
反證：若 $l_i>l_{i+1}$ 且都不為 $+\infty$，則 $(P_i,Q_{l_{i+1}},Q_{l_i},P_{i+1})$ 四個點構成 $H$.
若 $l_i=+\infty$，則由于入度不為 $0$，$P_1$ 一定滿足 $l_1=+\infty$，即 $(Q_{|Q|},P_1)$. 而因為 $(P_i,Q_{|Q|}),(Q_{|Q|},P_{i+1})$ 故 $(P_1,P_i,Q_{|Q|},P_{i+1})$ 構成 $H$.

還有一個問題：$dis(Q_j,P_i)$ 在 $(P_i,Q_j)$ 有邊時的距離沒有解決。由于整張圖中沒有入度大于 $X$ 的點，故 $Q$ 中每個點會往 $P$ 中連至少一條邊。而因為 $Q$ 往 $P$ 連的點是 $P$ 的一個前綴，因此一定會連到 $P_1$，故 $dis(Q_j,P_i)=2$.

最后總結一下結論：
$dis(P_i,P_j)=1?i<j$
$dis(P_i,P_j)=2?j<i\wedge |inQ(P_i)|=|inQ(P_j)|$
$dis(P_i,P_j)=3?j<i\wedge |inQ(P_i)|=|inQ(P_j)|$
$dis(Q_i,Q_j)=1?i<j$
$dis(Q_i,Q_j)=2?j<i\wedge |inP(Q_i)|=|inP(Q_j)|$
$dis(Q_i,Q_j)=3?j<i\wedge |inP(Q_i)|=|inP(Q_j)|$
$dis(P_i,Q_j)+dis(Q_j,P_i)=3$

時間復雜度 $O(n^2)$.

代碼

#include<bits/stdc++.h> #define llong long long #define mkpr make_pair #define x first #define y second #define iter iterator #define riter reversed_iterator #define y1 Lorem_ipsum_dolor using namespace std;inline int read() {int x = 0,f = 1; char ch = getchar();for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}return x*f; }const int mxN = 8000; int ind[mxN+3]; vector<int> s1,s2; char a[mxN+3][mxN+3]; queue<int> que; int n; llong w,ans;char decode(char x) {return x>=65?x-55:x-48;}bool cmp(int x,int y) {return a[x][y];}int main() {scanf("%d",&n); w = 614ll*n;for(int i=1; i<=n; i++){char ch = getchar();for(int j=4; j<=n; j+=4){ch = decode(getchar());a[i][j-3] = (ch&8)>>3,a[i][j-2] = (ch&4)>>2,a[i][j-1] = (ch&2)>>1,a[i][j] = ch&1;}}for(int i=1; i<=n; i++) for(int j=i+1; j<=n; j++){if(a[i][j]) {ind[j]++;} else {ind[i]++;}}for(int i=1; i<=n; i++) if(ind[i]==0) {que.push(i);}int cur = n;while(!que.empty()){int u = que.front(); que.pop();cur--; ans += (w+1ll)*cur;for(int v=1; v<=n; v++) if(a[u][v]&&v!=u){ind[v]--;if(ind[v]==0) {que.push(v);}}}if(cur==0) {printf("%I64d\n",ans); return 0;}int u = 0; for(int i=1; i<=n; i++) if(u==0||ind[i]>ind[u]) {u = i;}for(int i=1; i<=n; i++) if(ind[i]) {if(u==i||a[i][u]) {s1.push_back(i);} else {s2.push_back(i);}}sort(s1.begin(),s1.end(),cmp); sort(s2.begin(),s2.end(),cmp);ans += 3ll*s1.size()*s2.size()+s1.size()*(s1.size()-1ll)/2ll+s2.size()*(s2.size()-1ll)/2ll;for(int i=0; i<s1.size(); i++) {ind[s1[i]] -= i;}for(int i=0; i<s1.size(); i++) for(int j=0; j<i; j++){ans += ind[s1[i]]==ind[s1[j]]?3ll:2ll;}for(int i=0; i<s2.size(); i++) {ind[s2[i]] -= i;}for(int i=0; i<s2.size(); i++) for(int j=0; j<i; j++){ans += ind[s2[i]]==ind[s2[j]]?3ll:2ll;}printf("%I64d\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的Codeforces 1338E JYPnation (图论)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。