CF475E Strongly Connected City 2

題目描述

想象有一座城市，這座城市有 \(n\) 個路口和 \(m\) 條街道。路口編號從 \(1\) 到 \(n\)。

為了提高交通流量，市長決定將每條街道改為單行道。這意味著在連接路口 \(u\) 和 \(v\) 的街道上，交通只能從 \(u\) 到 \(v\)，或只能從 \(v\) 到 \(u\) 單向通行。

現(xiàn)在的問題是，需要為這些街道指定單向通行的方向，使得能夠到達的點對 \((u, v)\) 的數(shù)量最大，其中 \(1 \le u, v \le n\)，且要求從 \(u\) 出發(fā)經(jīng)過指定方向的街道能夠到達 \(v\)。你的任務是找出最大可能的此類點對數(shù)量。

題解：

先大概猜猜，發(fā)現(xiàn)一個簡單的性質，對于一個環(huán)，一定滿足全部都一個方向最優(yōu)秀。

所以我們先做一個 tarjan。點權為環(huán)的點數(shù)。然后發(fā)現(xiàn)貪心不大行，考慮 dp。

這個時候還要一個性質，對于最優(yōu)解。就是在只在重心上，能滿足其一部分子樹的所有點能到達他，其他點都可以從他到達。

證明：

考慮有一個小聯(lián)通快所有邊的方向與其他不同，那么發(fā)現(xiàn)把這個所有邊全部翻轉過來，答案一定變大，因為重心一側的點至少為所有點的一半。

這下就可以 dp 了。我們把重心作為根，考慮每個點的貢獻是多少：

• （除 \(root\)）自己 \(\times\) 自己的子樹和

• 通過重心的到達另一端

其實就是要判斷那些子樹進入，那些子樹要出去。

我們發(fā)現(xiàn)第一個貢獻不論怎么分配都是一樣的。

第二個貢獻實際上是一個數(shù)學問題：設你進入的節(jié)點總數(shù)為 \(x\)，重心點權為 \(y\) 另一側點的數(shù)量和為 \(z\)。那么有答案為 \((x+y)\times (y+z)\)。

那其實就是要找到每一個 \(x\) 能不能被表示出來，這是一個典型的 01背包 直接做復雜度 \(O(n^2)\) 用bitset 維護的話是 \(\frac{n^2}{w}\) 的。

code：

#include<bits/stdc++.h>
#define pb push_back
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int N=2e5+10;
int n,m,k,T,a[N],vis[N],dfn[N];
int low[N],tot,col,scc[N],siz[N];
int rt,mx=INT_MAX,sz[N],ans,sum;
vector<int> g[N],g1[N];
stack<int> st;
void tar(int u,int fa){
	dfn[u]=low[u]=++tot;
	vis[u]=1;st.push(u);
	for(int v:g[u]){
		if(v==fa) continue;
		if(!dfn[v]){
			tar(v,u);
			low[u]=min(low[u],low[v]);
		}else if(vis[v]) low[u]=min(low[u],dfn[v]);
	}if(low[u]==dfn[u]){
		col++;
		while(1){
			int t=st.top();st.pop();
			scc[t]=col;vis[t]=0;siz[col]++;
			if(t==u) break;
		}
	}
}
void getrt(int u,int fa){
	sz[u]=siz[u];int res=0;
	for(int v:g1[u]){
		if(v==fa) continue;
		getrt(v,u);
		sz[u]+=sz[v];res=max(res,sz[v]);
	}res=max(res,n-sz[u]);
	if(res<mx) mx=res,rt=u;
}
void dfs(int u,int fa){
	sz[u]=siz[u];
	for(int v:g1[u]){
		if(v==fa) continue;
		dfs(v,u);sz[u]+=sz[v];
	}if(fa)sum+=siz[u]*sz[u];
}
bitset<N> s; 
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	rep(i,1,m){
		int u,v;cin>>u>>v;
		g[u].pb(v);g[v].pb(u);
	}tar(1,0);
	rep(i,1,n){
		for(int v:g[i]){
			if(scc[i]!=scc[v]){
				g1[scc[i]].pb(scc[v]);
			}
		}
	}
	rt=0;getrt(1,0);dfs(rt,0);s[0]=1;
	if(g1[rt].size()==n-1){
		cout<<1ll*((n-1)/2)*(n-((n-1)/2))+(n-((n-1)/2)-1)+n;
		return 0;	
	}
	for(int v:g1[rt]){
		s=s|(s<<sz[v]);
	}rep(i,0,n){
		if(s[i]==1){
			ans=max(ans,(i+siz[rt])*(n-i));
		}
	}cout<<ans+sum;
	return 0;
}