AOJ2338 よくわかる二重魔法

AOJ

問題:
Intelligible Double Magic | Aizu Online Judge

要約すると、N頂点M辺の無向グラフが与えられるので好きに辺を有向にして(u,v)...uからvにいける ような組を多くせよ、という問題(N<=100,M<=N_C_2)





lowlinkを使って二重辺連結成分分解し重みつき木にしてdpすれば求めることができる
DEGwerが言っていたので考えてみたけど、ループの中身を見るとよくある木dp(O(n^3)と思いきやO(n^2)だった系の要素
(参考:二乗の木 DP - (iwi) ｛ 反省します - TopCoder部)
があるのでO(n^4)->O(n^3)な気がする。違うかも。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)

int n,m;
int szt[110],cmp[110],sz[110];
map<string,int> T;
vector<int> g[110],g2[110];
pii es[5010];
int now,ret;
int vis[110],ord[110],low[110],br[110][110];

void dfs(int v,int p){
    vis[v]=1;
    ord[v]=low[v]=now++;
    for(int &to:g[v])if(to!=p){
	if(!vis[to]){
	    dfs(to,v);
	    low[v]=min(low[v],low[to]);
	    if(ord[v]<low[to])br[v][to]=br[to][v]=1;
	}else low[v]=min(low[v],ord[to]);
    }
}

void dfs2(int v){
    vis[v]=szt[v]=1;
    for(int &to:g[v]){
	if(!vis[to]&&!br[v][to]){
	    dfs2(to);
	    szt[v]+=szt[to];
	}
    }
}

void dfs3(int v,int k){
    sz[now]=k;
    cmp[v]=now;
    vis[v]=1;
    for(int &to:g[v])
	if(!vis[to]&&!br[to][v])
	    dfs3(to,k);
}

int dp[110][110][110],m1[110][110],m2[110][110],wg[110];

void DFS(int v,int p){
    dp[v][sz[v]][sz[v]]=sz[v]*sz[v];
    wg[v]=sz[v];
    for(int &to:g2[v])if(to!=p){
	DFS(to,v);
	for(int i=wg[v];i;--i){
	    for(int j=wg[v];j;--j){
		if(dp[v][i][j]==0)continue;
		for(int k=wg[to];k;--k){
		    int x=m1[to][k];
		    if(x)dp[v][i+k][j]=max(dp[v][i+k][j],dp[v][i][j]+x+j*k);
		    x=m2[to][k];
		    if(x)dp[v][i][j+k]=max(dp[v][i][j+k],dp[v][i][j]+x+i*k);
		}
	    }
	}
	wg[v]+=wg[to];
    }
    rep(i,110)rep(j,110){
	m1[v][i]=max(m1[v][i],dp[v][i][j]);
	m2[v][j]=max(m2[v][j],dp[v][i][j]);
    }
}

main(){
    cin>>n>>m;
    string s;
    rep(i,n)cin>>s,T[s]=i;
    rep(i,m){
	string a,b;
	cin>>a>>b;
	int p=T[a],q=T[b];
	g[p].pb(q);g[q].pb(p);
	es[i]=mp(p,q);
    }
    dfs(0,-1);
    now=0;
    rep(i,n)vis[i]=0;
    rep(i,n)if(!vis[i])dfs2(i);
    rep(i,n)vis[i]=0;
    rep(i,n)if(!vis[i]){
	dfs3(i,szt[i]);
	now++;
    }
    rep(i,m){
	int p=cmp[es[i].first],q=cmp[es[i].second];
	if(p!=q)g2[p].pb(q),g2[q].pb(p);
    }
    DFS(0,-1);
    rep(i,110)rep(j,110)ret=max(ret,dp[0][i][j]);
    cout<<ret<<endl;
}