P1111 修复公路

肖邦 g 小调第一叙事曲

并查集 + \(krustra\) 板子题
code：

#include<bits/stdc++.h>

using namespace std;

const int maxn=1010;
const int maxm=100100; 

int n,m;
int en=0;
int ans=-1;
int to[maxn];

inline int read()
{
	int f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-48;
		ch=getchar();
	}
	return f*x;
}

struct edge{
	int p1,p2,d;
}ed[maxm];

bool operator<(const edge &a,const edge &b)
{
	return a.d<b.d;
}

int go(int p)
{
	if(p==to[p])return to[p];
	else return to[p]=go(to[p]); 
}

int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++)
	{
		to[i]=i;
	}
	for(int i=1;i<=m;i++)
	{
		ed[i].p1=read(),ed[i].p2=read(),ed[i].d=read();
	}
	sort(ed+1,ed+1+m);
	for(int i=1;i<=m;i++)
	{
		int p1=ed[i].p1,p2=ed[i].p2;
		if(go(p1)!=go(p2))
		{
			to[go(p1)]=to[go(p2)];
			en++;
			ans=max(ed[i].d,ans); 
		}
	}
	if(en==n-1)cout<<ans<<endl;
	else cout<<-1<<endl;
	return 0;
 } //第一次 m、n 写反喜提 10 分

P1123 取数游戏

(秀一下我新学的 \(LaTeX\) 不过分吧 qwq)

これから、我が剣は汝と共にあり、汝の運命は我とともに存続する。

题意：

有 \(T\) 组数据；
每组数据给你一个 \(N \times M\) 的矩阵，选择若干个不相邻的元素使它们的和最大，求出这个最大的和。
\(1 \le N\)、\(M \le 6\)，\(T \le 20\)。
不相邻是指 左、右、上、下、左上、左下、右上、右下 八个方向不相邻。

思路：

一看到 \(N\) 和 \(M\) 的取值范围，就知道这个题肯定是 爆搜！
那怎么搜索呢？
对于每一个数，我们有选择跟不选两种情况；
如果不选，可以继续搜索其他合法数。
如果选，那么我们就不能再选择它周围的数了，标记一下。
code:

#include<bits/stdc++.h>

using namespace std;

const int maxn=10;
const int maxm=10; //好习惯

int t;
int m,n;
int ans=0;
int mp[maxn][maxm];
int dx[]={0,1,-1,0,0,1,-1,1,-1};
int dy[]={0,-1,1,-1,1,1,-1,0,0}; //方向坐标 
int mark[maxn][maxm];

void dfs(int x,int y,int sum)
{
	if(y>m){
		dfs(x+1,1,sum);
		return;
	}
	if(x>n){
		ans=max(ans,sum);
		return;
	}
	//两种情况 
	dfs(x,y+1,sum); //不选的时候 
	if(!mark[x][y]) //选择的时候 
	{
		for(int i=1;i<=8;i++)
		{
			int xx=x+dx[i],yy=y+dy[i];
			mark[xx][yy]+=1; //将周围数的 mark +1
			//这个地方不能用 vis 判断是否遍历过，因为它也可能是其他被选择的数的相邻数 
		}
		dfs(x,y+1,sum+mp[x][y]); //sum 的值加上 选择的 这个数 
		for(int i=1;i<=8;i++)
		{
			int xx=x+dx[i],yy=y+dy[i]; //回溯 
			mark[xx][yy]-=1;
		}
	 } 
}

int main()
{
	cin>>t;
	while(t--)
	{
		ans=0;
		memset(mp,0,sizeof(mp));
		memset(mark,0,sizeof(mark)); //每次一定要清空 
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				cin>>mp[i][j];
			}
		}
		dfs(1,1,0);
		cout<<ans<<endl;
	}
	return 0; 
}（参考题解过的TAT，我太菜了）