A. Min-Fund Prison (Medium)
考虑一个边双连通分量一定不可能分为合法的两部分，于是进行缩点。缩完后显然是一个森林。
设 \(dp_{i,j,0/1}\) 表示第一堆有 \(i\) 个点，第二堆有 \(j\) 个点，两堆点有没有用一条边连起来的最小花费。对于每棵树，考虑将它加入第一堆/加入第二堆/一部分加入第一堆另一部分加入第二堆。时间复杂度 \(O(n^3)\)。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define pb push_back
#define mem(a,b) memset(a,b,sizeof a)
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
namespace IO{
const int bufsz=1<<20;
char ibuf[bufsz],*p1=ibuf,*p2=ibuf;
#define getchar() (p1==p2&&(p2=(p1=ibuf)+fread(ibuf,1,bufsz,stdin),p1==p2)?EOF:*p1++)
template<typename T=int>il T read(){
char ch=getchar();
while(ch<'0'||ch>'9'){
ch=getchar();
}
T x=0;
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x;
}
#undef getchar
char obuf[bufsz],*p3=obuf,s[50];
il int flush(){
fwrite(obuf,1,p3-obuf,stdout);
p3=obuf;
return 0;
}
#define putchar(ch) (p3==obuf+bufsz&&flush(),*p3++=(ch))
template<typename T>il void write(T x,bool typ=1){
if(x<0){
putchar('-');
x=-x;
}
int top=0;
do{
s[++top]=x%10|48;
x/=10;
}while(x);
while(top){
putchar(s[top--]);
}
putchar(typ?'\n':' ');
}
#undef putchar
}
using IO::read;
using IO::write;
const int maxn=305,inf=0x3f3f3f3f3f3f3f3f;
int T,n,m,c,enm,hd[maxn];
struct edge{
int v,nxt;
}e[maxn<<1];
il void addedge(int u,int v){
e[++enm]=(edge){v,hd[u]};
hd[u]=enm;
}
int dfn[maxn],low[maxn],cnt;
bool geb[maxn<<1];
il void tarjan(int u,int fa){
dfn[u]=low[u]=++cnt;
for(int i=hd[u],v;i;i=e[i].nxt){
v=e[i].v;
if(!dfn[v]){
tarjan(v,i);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u]){
geb[i]=geb[i^1]=1;
}
}
else if(i!=fa&&i!=(fa^1)){
low[u]=min(low[u],dfn[v]);
}
}
}
int bel[maxn],bcn,sz[maxn];
bool vis[maxn];
il void dfs1(int u){
vis[u]=1,bel[u]=bcn,sz[bcn]++;
for(int i=hd[u],v;i;i=e[i].nxt){
v=e[i].v;
if(!vis[v]&&!geb[i]){
dfs1(v);
}
}
}
int dp[maxn][maxn][2],nf[maxn][maxn][2],tot;
vector<int> ed[maxn];
il void dfs2(int u,int fa){
vis[u]=1;
for(int v:ed[u]){
if(v==fa){
continue;
}
dfs2(v,u);
sz[u]+=sz[v];
}
}
il void upd(int &x,int y){
x=min(x,y);
}
il void dfs3(int u,int fa,int rt){
for(int v:ed[u]){
if(v==fa){
continue;
}
for(int i=0;i<=tot;i++){
upd(nf[i+sz[v]][tot-i+sz[rt]-sz[v]][1],dp[i][tot-i][0]+2*i*sz[v]+sz[v]*sz[v]+2*(tot-i)*(sz[rt]-sz[v])+(sz[rt]-sz[v])*(sz[rt]-sz[v])+c*(i?1:0)+c*(tot-i?1:0));
upd(nf[i+sz[rt]-sz[v]][tot-i+sz[v]][1],dp[i][tot-i][0]+2*i*(sz[rt]-sz[v])+(sz[rt]-sz[v])*(sz[rt]-sz[v])+2*(tot-i)*sz[v]+sz[v]*sz[v]+c*(i?1:0)+c*(tot-i?1:0));
}
dfs3(v,u,rt);
}
}
il void solve(){
n=read(),m=read(),c=read();
enm=1;
for(int i=1,u,v;i<=m;i++){
u=read(),v=read();
addedge(u,v);
addedge(v,u);
}
cnt=0;
for(int i=1;i<=n;i++){
if(!dfn[i]){
tarjan(i,0);
}
}
bcn=0;
for(int i=1;i<=n;i++){
if(!vis[i]){
bcn++;
dfs1(i);
}
}
// for(int i=1;i<=bcn;i++){
// cout<<sz[i]<<" ";
// }
// puts("");
for(int u=1;u<=n;u++){
for(int i=hd[u],v;i;i=e[i].nxt){
v=e[i].v;
if(bel[u]!=bel[v]){
ed[bel[u]].pb(bel[v]);
ed[bel[v]].pb(bel[u]);
}
}
}
for(int i=1;i<=bcn;i++){
sort(ed[i].begin(),ed[i].end());
ed[i].erase(unique(ed[i].begin(),ed[i].end()),ed[i].end());
}
mem(dp,0x3f);
dp[0][0][0]=0;
tot=0;
mem(vis,0);
for(int i=1;i<=bcn;i++){
if(!vis[i]){
// cout<<i<<"\n";
dfs2(i,0);
memcpy(nf,dp,sizeof dp);
for(int j=0;j<=tot;j++){
upd(nf[j+sz[i]][tot-j][0],dp[j][tot-j][0]+2*j*sz[i]+sz[i]*sz[i]+c*(j?1:0));
upd(nf[j][tot-j+sz[i]][0],dp[j][tot-j][0]+2*(tot-j)*sz[i]+sz[i]*sz[i]+c*(tot-j?1:0));
upd(nf[j+sz[i]][tot-j][1],dp[j][tot-j][0]+2*j*sz[i]+sz[i]*sz[i]+c+c*(j?1:0));
upd(nf[j+sz[i]][tot-j][1],dp[j][tot-j][1]+2*j*sz[i]+sz[i]*sz[i]+c*(j?1:0));
upd(nf[j][tot-j+sz[i]][1],dp[j][tot-j][0]+2*(tot-j)*sz[i]+sz[i]*sz[i]+c+c*(tot-j?1:0));
upd(nf[j][tot-j+sz[i]][1],dp[j][tot-j][1]+2*(tot-j)*sz[i]+sz[i]*sz[i]+c*(tot-j?1:0));
}
dfs3(i,0,i);
tot+=sz[i];
memcpy(dp,nf,sizeof nf);
}
}
// cout<<tot<<"\n";
int ans=inf;
for(int i=1;i<tot;i++){
ans=min(ans,dp[i][tot-i][1]);
}
write(ans>=inf?-1:ans);
mem(hd,0),mem(dfn,0),mem(low,0);
mem(vis,0),mem(geb,0),mem(sz,0);
for(int i=1;i<=bcn;i++){
ed[i].clear();
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
T=read();
while(T--){
solve();
}
IO::flush();
return 0;
}
}
signed main(){return asbt::main();}
/*
1
6 6 2
1 4
2 5
3 6
1 5
3 5
6 5
*/