首页 > 其他分享 >ABC338 F

ABC338 F

时间：2024-01-29 19:58:01浏览次数：45  
标签：ABC338 int void maxn inline dp define

link

观察到 \(n\) 的范围不大，考虑状压。

\(dp_{i,S}\) 表示在经过顶点集合状态为 \(S\) 的情况下，终点为 \(i\) 的最小步数。

错误示范：

考虑对于状态 \(S\) ，直接遍历经过的顶点 \(i\) ，枚举 \(i\) 的出边进行转移。


#include<bits/stdc++.h>

typedef long long LL;
typedef std::pair<int,int> pii;

#define fi first
#define se second
#define ok putstrln("OrzFinderHT")
//#define check_time printf("%.8f\n",clocks()/CLOCK_PER_SEC)

template<typename T>
void abs(T &N){
	if(N>=0) N=N;
	else N=-N;
}

namespace G_{
	template<typename T>
	inline void read(T &a){
		a=0;
		int f=1;
		char c=getchar();
		while(c<'0'||c>'9'){
			if(c=='-') f=-1;
			c=getchar();
		}
		while(c>='0'&&c<='9') a=a*10+(int)(c-'0'),c=getchar();
		a*=f;
	}
	inline void get_enter(){
		getchar();
	}
	inline void get_str(std::string &str){
		char c=getchar();
		while(c!=' '&&c!='\n') str+=c,c=getchar();
	}
	template<typename T>
	inline void putN(T N){
		char stk[70];
		short top=0;
		if(N<0) putchar('-'),abs(N);
		do{
			stk[++top]=(char)(N%10+(int)'0');
			N/=10;
		}while(N);
		while(top) putchar(stk[top--]);
	}
	template<typename T>
	inline void putsp(T N){
		putN(N);
		putchar(' ');
	}
	template<typename T>
	inline void putln(T N){
		putN(N);
		putchar('\n');
	}
	inline void putstr(std::string str){
		int sz=str.size()-1;
		for(int i=0;i<=sz;i++) putchar(str[i]);
	}
	inline void putstrln(std::string str){
		putstr(str);
		putchar('\n');
	}
	inline void Yes(){
		putstrln("Yes");
	}
	inline void No(){
		putstrln("No");
	}
	template<typename T,typename I>
	inline void chkmin(T &a,I b){
		a=std::min(a,b);
	}
}

//using namespace get_give;

using namespace G_;

const LL maxn=25,maxs=1<<20,inf=1e9;

std::vector<pii>d[maxn];

LL dp[maxn][maxs];

signed main(){
	int n,m;
	read(n),read(m);
	for(int i=1;i<=m;i++) {
		int u,v,w;
		read(u),read(v),read(w);
		d[u].push_back({v,w});
	}
	int S=(1<<n)-1;
	memset(dp,0x3f,sizeof(dp));
	for(int i=1;i<=n;i++) dp[i][(1<<(i-1))]=0;
	for(int s=1;s<S;s++)
		for(int i=1;i<=n;i++){
			if(!((1<<(i-1))&s)) continue;
			for(auto q:d[i]){
//				if((1<<(q.fi-1))&s) continue;
				int g=s|(1<<(q.fi-1));
				chkmin(dp[q.fi][g],dp[i][s]+q.se);
//				printf("##%d %d %d %d !!%d\n",q.fi,g,i,s,dp[q.fi][g]);
			} 
		}
	LL ans=inf;
	for(int i=1;i<=n;i++) chkmin(ans,dp[i][S]);//,printf("&&&%d %d\n",i,ans);
	if(ans==inf){
		printf("No");
		return 0;
	}
	printf("%lld\n",ans);
//	putN(ans);
	return 0;
}
/*
-读入字符一定检查回车
- 能不能搜索？
-函数要有返回值！
-想好了再写！
*/

由于存在值为负的路径，所以使得我们重复经过一些边可以让答案更优。比如对于 11010 ，我们的转移一定来自 11000 或 10010 或 01010 。但是注意，当我们在 11010 这个状态到达 #2 时，若连接 #2 和 #4 的边是负的，那么我们可以通过这条边，使得 11010 状态下代价变小。

那如果我们允许从一个访问过的点到达另一个访问过的点呢？

还是对于 11010 ，我们会按照 $ 2\rightarrow 4\rightarrow 5$ 的顺序来访问已知点，令 \(w(i,j)\) 表示连接 \(i\) 和 \(j\) 两点的边的权值，如果 \(w(5,2)+w(2,4)<0\) ，那么我们又会得到一个更小的 11010 状态下的代价，但是遗憾的是，当我们由 \(5\) 更新到 \(2\) 时，无法再退回去进一步更新。

我们又想到，可以用队列记录可能更新其它状态的状态，类似 dij 那样，但是如果用队列处理，会导致时间复杂度过大。

但是发现，只会有三个点 TLE ，且时间只比时限多出 0.6s(link)，运用一些随机化技巧或许可以通过，可以自行尝试。


#include<bits/stdc++.h>

typedef long long LL;
typedef std::pair<int,int> pii;

#define fi first
#define se second
#define ok putstrln("OrzFinderHT")
//#define check_time printf("%.8f\n",clocks()/CLOCK_PER_SEC)

template<typename T>
void abs(T &N){
	if(N>=0) N=N;
	else N=-N;
}

namespace G_{
	template<typename T>
	inline void read(T &a){
		a=0;
		int f=1;
		char c=getchar();
		while(c<'0'||c>'9'){
			if(c=='-') f=-1;
			c=getchar();
		}
		while(c>='0'&&c<='9') a=a*10+(int)(c-'0'),c=getchar();
		a*=f;
	}
	inline void get_enter(){
		getchar();
	}
	inline void get_str(std::string &str){
		char c=getchar();
		while(c!=' '&&c!='\n') str+=c,c=getchar();
	}
	template<typename T>
	inline void putN(T N){
		char stk[70];
		short top=0;
		if(N<0) putchar('-'),abs(N);
		do{
			stk[++top]=(char)(N%10+(int)'0');
			N/=10;
		}while(N);
		while(top) putchar(stk[top--]);
	}
	template<typename T>
	inline void putsp(T N){
		putN(N);
		putchar(' ');
	}
	template<typename T>
	inline void putln(T N){
		putN(N);
		putchar('\n');
	}
	inline void putstr(std::string str){
		int sz=str.size()-1;
		for(int i=0;i<=sz;i++) putchar(str[i]);
	}
	inline void putstrln(std::string str){
		putstr(str);
		putchar('\n');
	}
	inline void Yes(){
		putstrln("Yes");
	}
	inline void No(){
		putstrln("No");
	}
	template<typename T,typename I>
	inline void chkmin(T &a,I b){
		a=std::min(a,b);
	}
}

//using namespace get_give;

using namespace G_;

const LL maxn=25,maxs=1<<20,inf=1e9;

std::vector<pii>d[maxn];

LL dp[maxn][maxs];

std::queue<pii>q;

signed main(){
	int n,m;
	read(n),read(m);
	for(int i=1;i<=m;i++) {
		int u,v,w;
		read(u),read(v),read(w);
		d[u].push_back({v,w});
	}
	int S=(1<<n)-1;
	memset(dp,0x3f,sizeof(dp));
	for(int i=1;i<=n;i++) dp[i][(1<<(i-1))]=0,q.push({i,1<<(i-1)});
	while(q.size()){
		int s=q.front().se,i=q.front().fi;
		q.pop();
		for(int flag=1;flag;flag--){
			if(!((1<<(i-1))&s)) continue;
			for(auto qq:d[i]){
//				if((1<<(q.fi-1))&s) continue;
				int g=s|(1<<(qq.fi-1));
				if(dp[qq.fi][g]>dp[i][s]+qq.se) q.push({qq.fi,g});
				chkmin(dp[qq.fi][g],dp[i][s]+qq.se);
//				printf("##%d %d %d %d !!%d\n",q.fi,g,i,s,dp[q.fi][g]);
			} 
		}
	}
	LL ans=inf;
	for(int i=1;i<=n;i++) chkmin(ans,dp[i][S]);//,printf("&&&%d %d\n",i,ans);
	if(ans==inf){
		printf("No");
		return 0;
	}
	printf("%lld\n",ans);
//	putN(ans);
	return 0;
}
/*
-读入字符一定检查回车
- 能不能搜索？
-函数要有返回值！
-想好了再写！
*/

参见：link

正确示范：

考虑用 floyd 先处理出来两点之间的最短路，然后不枚举连边，直接对所有点更新，可以避免上面那种情况。

但是，我们注意到如果从 \(i\) 向 \(j\) 更新，且两者不存在直接连边，那样就会经过一些没有访问过的点，这些点不会被记录进状态中，这样是否会造成答案错误？

显然是不会的，设当前状态为 \(S\) ，按照我们的方法，能保证所有 \(/le S\) 的状态是正确的。对于后面的状态，经过感性理解可以发现也是没有影响的。

官方题解中先给出了一段看似显然的证明，或许意在利用 dp 的最优子结构性质来进行 dp ，但说明不够充分，大部分还需要感性理解。（显然，我的题解更适合作为官方题解）。


#include<bits/stdc++.h>

typedef long long LL;
typedef std::pair<int,int> pii;

#define fi first
#define se second
#define ok putstrln("OrzFinderHT")
//#define check_time printf("%.8f\n",clocks()/CLOCK_PER_SEC)

template<typename T>
void abs(T &N){
	if(N>=0) N=N;
	else N=-N;
}

namespace G_{
	template<typename T>
	inline void read(T &a){
		a=0;
		int f=1;
		char c=getchar();
		while(c<'0'||c>'9'){
			if(c=='-') f=-1;
			c=getchar();
		}
		while(c>='0'&&c<='9') a=a*10+(int)(c-'0'),c=getchar();
		a*=f;
	}
	inline void get_enter(){
		getchar();
	}
	inline void get_str(std::string &str){
		char c=getchar();
		while(c!=' '&&c!='\n') str+=c,c=getchar();
	}
	template<typename T>
	inline void putN(T N){
		char stk[70];
		short top=0;
		if(N<0) putchar('-'),abs(N);
		do{
			stk[++top]=(char)(N%10+(int)'0');
			N/=10;
		}while(N);
		while(top) putchar(stk[top--]);
	}
	template<typename T>
	inline void putsp(T N){
		putN(N);
		putchar(' ');
	}
	template<typename T>
	inline void putln(T N){
		putN(N);
		putchar('\n');
	}
	inline void putstr(std::string str){
		int sz=str.size()-1;
		for(int i=0;i<=sz;i++) putchar(str[i]);
	}
	inline void putstrln(std::string str){
		putstr(str);
		putchar('\n');
	}
	inline void Yes(){
		putstrln("Yes");
	}
	inline void No(){
		putstrln("No");
	}
	template<typename T,typename I>
	inline void chkmin(T &a,I b){
		a=std::min(a,b);
	}
}

//using namespace get_give;

using namespace G_;

const LL maxn=25,maxs=1<<20,inf=1e9;

std::vector<pii>d[maxn];

LL dp[maxn][maxs];

int dis[maxn][maxn];

signed main(){
	int n,m;
	read(n),read(m);
	memset(dis,0x3f,sizeof(dis));
	for(int i=1;i<=m;i++) {
		int u,v,w;
		read(u),read(v),read(w);
		dis[u][v]=w;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			for(int k=1;k<=n;k++) chkmin(dis[i][j],dis[i][k]+dis[k][j]); 
	int S=(1<<n)-1;
	memset(dp,0x3f,sizeof(dp));
	for(int i=1;i<=n;i++) dp[i][(1<<(i-1))]=0;
	for(int s=1;s<S;s++)
		for(int i=1;i<=n;i++){
			if(!((1<<(i-1))&s)) continue;
			for(int j=1;j<=n;j++){
//				if((1<<(q.fi-1))&s) continue;
				int g=s|(1<<(j-1));
				chkmin(dp[j][g],dp[i][s]+dis[i][j]);
//				printf("##%d %d %d %d !!%d\n",q.fi,g,i,s,dp[q.fi][g]);
			} 
		}
	LL ans=inf;
	for(int i=1;i<=n;i++) chkmin(ans,dp[i][S]);//,printf("&&&%d %d\n",i,ans);
	if(ans==inf){
		printf("No");
		return 0;
	}
	printf("%lld\n",ans);
//	putN(ans);
	return 0;
}
/*
-读入字符一定检查回车
- 能不能搜索？
-函数要有返回值！
-想好了再写！
*/

时间复杂度

参见此贴 。

贴中 rui_er 指出状压 dp 基础复杂度就是 \(O(2^(n-1)\times n)\) ，但至于“常数巨大”，我并没有发现什么常数。

本题的最优复杂度为 \(O(n^3+2^{n-1}\times n^2)\) （lowbit 逐位分解），但在通常实现方式下为 \(O(n^3+2^n\times n^2)\) 。

标签：ABC338,int,void,maxn,inline,dp,define
From： https://www.cnblogs.com/BYR-KKK/p/17995205

相关文章

  • 题解 [ABC338D] Island Tour
    【洛谷博客】被降智的一道简单题。题意\(n\)个岛屿，第\(i\)座桥连接\(i\)和\(i+1\)（第\(N\)座桥连接着\(1\)和\(N\)）。有一条长度为\(M\)的旅游序列\(X\)，你需要按照顺序依次经过这些点，选择断掉一座桥使得旅游经过的桥最少。分析设断掉第\(i\)座桥会因为绕行增......
  • ABC338D 题解
    赛时怎么连这题都不会。再不练练思维真的就连普及题都不会做了啊。Solution题目来源：ABC338D（inAtcoder|in洛谷）。不妨先考虑应该断掉哪条边。首先我们发现，仅断掉一条边并不会让两个结点不可达，只会让我们从一个结点绕更远的路到达目标结点。如果我们要从结点\(u\)前往结点......
  • ABC338 F Negative Traveling Salesman 题解
    QuestionABC338FNegativeTravelingSalesman给出一个\(N\)个点\(M\)条边的有向图，边权可能为负数，但不可能有负环每经过一条边就要加上这条边的代价求，一条路径经过所有的点，并且要求总代价最小Solution观察到\(N\le20\)自然而然想到状压因为多次经过一条边的代价是......
  • ABC338 D Island Tour 题解
    Question有\(n\)座海岛由\(n\)条桥连着，第\(i\)座桥连接第\(i\)和\(i+1\)座海岛，第\(n\)座桥连接第\(n\)和\(1\)座海盗有一条长度为\(m\)的旅游路线，第\(X_i\)表示依次到达的岛屿现在需要切断一条桥，求总旅游路线最小值Solution显然，从第\(X_{i-1}\)到\(X_......
  • ABC338 E Chords 题解
    Question一个圆上有\(2N\)个点均匀分布，给出\(N\)条线，每条线连接两个顶点问，有没有两条线相交Solution也算一个比较典的题目考虑到这种两两配对，配对中有没有交错关系的可以考虑异或哈希因为一个数异或两次等于它本身，所以我们可以用异或来实现一个“撤销”操作我们当我......
  • ABC338 题解（A-E）
    前言：F,G后续补充。A题意判断一个字符串，是否满足只有第一位为大写字母，其余为小写字母。Sol字面意思模拟即可。Code#include<bits/stdc++.h>#definelllonglong#defineN200005#defineendl"\n"#definefifirst#definesesecondusingnamespacestd;constll......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99