[AHOI2012]收集资源

C++(g++ 7.5.0) 解法, 执行用时: 426ms, 内存消耗: 540K, 提交时间: 2023-03-19 16:32:56

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
void read(int &x) {
    char ch; bool ok;
    for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;
    for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;
}
void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
#define rg register
const int maxn=210;
int n,m,T,ans,d[maxn][maxn];bool vis[maxn];
struct oo{int x,y,v;}a[maxn];
void dfs(int x,int now,int val)
{
	if(now<=T)ans=max(ans,val);
	else return ;
	for(rg int i=1;i<=m;i++)
		if(d[x][i]&&!vis[i])
			vis[i]=1,dfs(i,now+d[x][i],val+a[i].v),vis[i]=0;
}
int main()
{
	read(n),read(m),read(T);
	for(rg int i=1;i<=m;i++)read(a[i].x),read(a[i].y),read(a[i].v);
	for(rg int i=0;i<=m;i++)
		for(rg int j=0;j<=m;j++)
			if(i!=j) 
			{
				bool flag=0;
				for(rg int k=1;k<=m;k++)
					if(k!=i&&k!=j)
					{
						int lx=min(a[i].x,a[j].x),rx=max(a[i].x,a[j].x),ly=min(a[i].y,a[j].y),ry=max(a[i].y,a[j].y);
						if(a[k].x>=lx&&a[k].x<=rx&&a[k].y>=ly&&a[k].y<=ry){flag=1;break;}
					}
				if(!flag)d[i][j]=abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y);
			}
	dfs(0,0,0);printf("%d\n",ans);
}

C++14(g++5.4) 解法, 执行用时: 354ms, 内存消耗: 580K, 提交时间: 2020-09-28 19:23:45

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 210;
struct node{
	int x,y,w;
}a[maxn];
int n,m,t;
int dis[maxn][maxn];
bool check(int i,int j){
	int lx = min(a[i].x,a[j].x);
	int ly = min(a[i].y,a[j].y);
	int rx = max(a[i].x,a[j].x);
	int ry = max(a[i].y,a[j].y);
	for(int k=1;k<=m;k++){
		if(k==i||k==j) continue;
		if(a[k].x>=lx&&a[k].x<=rx&&a[k].y>=ly&&a[k].y<=ry) return 0;
	}
	return 1;
}
int ans,vis[maxn];
void dfs(int x,int res,int sum){
	ans = max(ans,sum);
	for(int i=1;i<=m;i++){
		if(x==i||vis[i]) continue;
		if(res-dis[x][i]<0) continue;
		vis[i] = 1;
		dfs(i,res-dis[x][i],sum+a[i].w);
		vis[i] = 0;
	}
}
int main(){
//	freopen("123.txt","r",stdin);
	scanf("%d%d%d",&n,&m,&t);
	memset(dis,0x3f,sizeof dis);
	m++;
	dis[1][1] = 0;
	for(int i=2;i<=m;i++){
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);
		dis[i][i] = 0;
	}
	for(int i=1;i<=m;i++){
		for(int j=i+1;j<=m;j++){
			if(check(i,j))
			dis[i][j] = dis[j][i] = min(dis[i][j],abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y));
		}
	}
	dfs(1,t,0);
	printf("%d",ans);
}

C++11(clang++ 3.9) 解法, 执行用时: 478ms, 内存消耗: 492K, 提交时间: 2019-04-30 20:15:00

#include<iostream>
#include<cstdio>
#include<ctype.h>
#include<cmath>
using namespace std;
inline int read(){
	int x=0,f=0;char ch=getchar();
	while(!isdigit(ch))f|=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
	return f?-x:x;
}
struct OOO {
    int x,y,w;
}a[205];
int n,m,T,ans,g[205][205],vis[205];
inline bool check(int x,int y){//哇哦，太漂亮的优化 
	int lx=max(a[x].x,a[y].x),ly=max(a[x].y,a[y].y),rx=a[x].x+a[y].x-lx,ry=a[x].y+a[y].y-ly;
	for(int i=0;i<=m;++i)if(i!=x && i!=y && a[i].x>=rx && a[i].x<=lx && a[i].y>=ry && a[i].y<=ly)return false;
	return true;
}
void dfs(int x,int t,int sum){
	ans=max(sum,ans);
	for(int i=0;i<=m;++i)
		if(g[x][i] && t+g[x][i]<=T && !vis[i])
			vis[i]=1,dfs(i,t+g[x][i],sum+a[i].w),vis[i]=0;
}
int main(){
	n=read(),m=read(),T=read();
	for(int i=1;i<=m;i++)a[i].x=read(),a[i].y=read(),a[i].w=read();   
	for(int i=0;i<=m;i++)
		for(int j=0;j<=m;j++)
			if(i!=j && check(i,j))g[i][j]=abs(a[j].y-a[i].y)+abs(a[j].x-a[i].x);
	dfs(0,0,0);
	printf("%d\n",ans);
	return 0;
}

详情