题解 Connect

各种骗分无果，特殊性质还手残写挂了……

首先完全图上直接输出边权 \(\times (n-2)\) 就行了，然而我脑残乘的 \(n-1\)

看数据范围肯定是状压，但是压边肯定炸了，考虑压点

因为1到n路径唯一，最终的图可以看作一条链上挂着数个连通块

根据题解，我们试着从这个方向下手

那这里状压的时候我们既要考虑这条链，又要考虑连通块

发现只有链上的最后一个元素有用，所以令 \(dp[s][k]\) 为已选的点集为 \(s\) ，链的末端为k时的最大边权和

考虑转移，发现我们可以向链的末端挂上一个任意大小的联通块

所以直接暴力 \(O(n^23^n)\) 枚举转移，发现T了

于是大力卡常，预处理优化到 \(O(\frac{n^2}{4}3^n)\) ，发现过了，然后就没有了

其实还可以优化，考虑把「挂任意大小的联通块」拆成「挂一个元素」和「在当前链的末端挂一个连通块，但不改变链的末端元素」两种情况

然后就可以分开转移，可以康康战神代码

Code:

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define N 100010

#define ll long long

#define reg register int

//#define int long long 

char buf[1<<21], *p1=buf, *p2=buf;

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)

inline int read() {

	int ans=0, f=1; char c=getchar();

	while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}

	while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}

	return ans*f;

}

int n, m;

ll sum;

namespace force{

	ll ans;

	int head[N], size;

	bool vis[N], use[N], fa[N];

	struct edge{int from, to, next, val;}e[N<<1];

	inline void add(int s, int t, int w) {edge* k=&e[++size]; k->from=s; k->to=t; k->val=w; k->next=head[s]; head[s]=size;}

	inline bool operator < (edge a, edge b) {return a.val<b.val;}

	inline int find(int p) {return fa[p]==p?p:fa[p]=find(fa[p]);}

	bool dfs(int u) {

		vis[u]=1;

		bool yes=0;

		for (int i=head[u],v; i; i=e[i].next) {

			v = e[i].to;

			if (!vis[v]) {

				if (dfs(v)) yes=1;

			}

		}

		if (yes) {

			use[u]=1;

			for (int i=head[u]; i; i=e[i].next)

				use[e[i].to]=1;

		}

		return (u==n)||yes;

	}

	void kruskal() {

		sort(e+1, e+size+1);

		for (int i=1,f1,f2; i<=size; ++i) {

			f1=find(e[i].from), f2=find(e[i].to);

			if (f1!=f2) {

				ans+=e[i].val;

			}

			else if (!(use[e[i].from]&&use[e[i].to])) ans+=e[i].val;

		}

	}

	void solve() {

		bool same=1; int lst=0;

		for (int i=1,u,v,w; i<=m; ++i) {

			u=read(); v=read(); w=read(); sum+=w;

			add(u, v, w); add(v, u, w);

			if (lst&&w!=lst) same=0;

			else lst=w;

		}

		dfs(1);

		if (same && m>=n*(n-1)/2) {printf("%lld\n", 1ll*lst*(n-2)); exit(0);}

		//for (int i=1; i<=n; ++i) cout<<use[i]<<' '; cout<<endl;

		kruskal();

		printf("%lld\n", sum-ans);

		exit(0);

	}

}

namespace task{

	ll dp[1<<16][16], sum[1<<16][16], tot;

	int mp[16][16], lg[1<<16];

	void solve() {

		for (int i=1,u,v; i<=m; ++i) {

			u=read()-1; v=read()-1;

			tot+=(mp[u][v]=mp[v][u]=read());

		}

		int lim=1<<n; ll tem;

		for (int i=0; i<n; ++i) lg[1<<i]=i;

		for (reg s=1; s<lim; ++s) {

			tem=0;

			for (reg i=0; i<n; ++i) if (s&(1<<i))

				for (reg j=i+1; j<n; ++j) if (s&(1<<j))

					tem+=mp[i][j];

			if (s&1) dp[s][0]=sum[s][0]=tem;

			else for (reg i=0; i<n; ++i) if (s&(1<<i)) sum[s][i]=tem;

		}

		for (reg s=1,s2; s<lim; ++s) {

			if (!(s&1)) continue;

			for (reg s0=s2=(~s)&(lim-1); s0; s0=(s0-1)&s2)

				for (reg i=s; i; i-=i&-i)

					for (reg j=s0; j; j-=j&-j)

						dp[s|s0][lg[j&-j]] = max(dp[s|s0][lg[j&-j]], dp[s][lg[i&-i]]+sum[s0][lg[j&-j]]+mp[lg[i&-i]][lg[j&-j]]);

				#if 0

				for (reg i=0; i<n; ++i) if (s&(1<<i))

					for (reg j=0; j<n; ++j) if (s0&(1<<j)&&mp[i][j]) {

						//if (dp[s][i]+sum[s0][j]+mp[i][j] > dp[s|s0][j]) cout<<"new ans"<<endl;

						dp[s|s0][j] = max(dp[s|s0][j], dp[s][i]+sum[s0][j]+mp[i][j]);

						//cout<<"upd "<<bitset<15>(s)<<' '<<bitset<15>(s0)<<' '<<i<<' '<<j<<' '<<dp[s][i]<<' '<<sum[s0][j]<<' '<<mp[i][j]<<endl;

					}

				#endif

		}

		//cout<<"dp: "<<dp[lim-1][n-1]<<endl;

		printf("%lld\n", tot-dp[lim-1][n-1]);

		exit(0);

	}

}

signed main()

{

	n=read(); m=read();

	task::solve();

	return 0;

}

巴特西

题解 Connect

最新文章

热门文章