[数据结构与算法] 9.9基础数图

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 9.9基础数图 -> 正文阅读

[数据结构与算法]9.9基础数图

	预期	一测	$\Delta$
a	100	100	0
b	100	100	0
c	100	100	0
d	100	100	0
e	20	0	-20
f	100	0	-100
g	100	100	0
h	0	0	0
总分	620	500	-120

问题 A: 查找二叉树(tree_a)

按题意建树，中序遍历就行了。

void bianli(int i){//中序遍历
	if(i!=0){
		bianli(t[i].l);
		m++;
		if(t[i].x==k) ans=m;
		bianli(t[i].r);
	}
}

for(int i=1;i<=n;i++){//建树
	int xx,lc,rc;
	scanf("%d%d%d",&xx,&lc,&rc);
	t[i].x=xx,t[i].l=lc,t[i].r=rc;
}

问题 B: 找树根和孩子

对于输入的每一个 x 和 y 记录son[x]++,fa[y]=x;然后先遍历根据树的性质，fa[i]==i 的节点即为根节点，son 最多的点即为目标点，然后在遍历所有点只要满足 fa[i]==j && i!=root 的点就输出。

son[x]++;fa[y]=x;

for(int i=1;i<=n;i++) if(fa[i]==i) root=i;
for(int i=1;i<=n;i++) if(son[i]>son[j]) j=i;
cout<<root<<endl<<j<<endl;
for(int i=1;i<=n;i++) if(fa[i]==j && i!=root) cout<<i<<" ";

?问题 C: 铲雪车(snow)

题目看起来确实难，但数据太水，是一定保证一笔画的。所以直接算。（注：正解我不会）

#include<bits/stdc++.h>
using namespace std;
long double solve(int a,int b,int c,int d) {
	long double x,y;
	x=abs(a-c);
	y=abs(b-d);
	return sqrt(x*x+y*y)/10000;
}
int mround(long double inp) {
	if(inp-floor(inp)>=0.5) return floor(inp)+1;
	else return floor(inp);
}
int sx,sy,ex,ey;
unsigned int h,m;
long double tot;
int main() {
	cin>>sx>>sy;
	while(scanf("%d%d%d%d",&sx,&sy,&ex,&ey)!=EOF)
		tot+=solve(sx,sy,ex,ey);
	h=floor(tot)-1;
	m=mround(60*(tot-h));
	h=m/60+h;
	m%=60;
	if(m>=60){m-=60;h++;}
	cout<<h<<":";
	if(m<10) cout<<"0";
	cout<<m<<endl;
	return 0;
}

问题 D: 分糖果(candy)

题意很简单，就是从 c 小朋友开始宽搜遍历，由于BFS的性质，一个点第一次搜到，那就是最短距离，其中找最大值加上 m 就行了。

#include<bits/stdc++.h>
using namespace std;
template <typename T>inline void read(T &x){
	T ch = getchar(), xx = 1; x = 0;
	while(!isdigit(ch)) xx = ch == '-' ? -1 : xx, ch = getchar();
	while(isdigit(ch)) x = (x<<3) + (x<<1) + ch - '0', ch = getchar();
	x *= xx;
}
#define N 100001
int nxt[N*22],to[N*22],head[N],cnt;
void build(int x,int y){
	to[++cnt]=y;
	nxt[cnt]=head[x];
	head[x]=cnt;
}
bool v[N];
queue<int> q;
int d[N];
int n,p,c,k,m,ans;
int main(){
	read(n);read(p);read(c);read(m);
	for(int i=1;i<=p;i++){
		int x,y;
		read(x),read(y);
		build(x,y),build(y,x);
	}
	q.push(c);
	v[c]=1;d[c]=1;
	while(q.size()){
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=nxt[i]){
			int y=to[i];
			if(!v[y]){
				v[y]=1;
				d[y]=d[x]+1;
				ans=max(ans,d[y]);
				q.push(y);
			}
		}
	}
	cout<<ans+m;
}

问题 E: 刻录光盘(cdrom)

刚看到题时，脑海里闪过强连通，单点，但100的数据，暴力 $n^3$ 方！Floyd ！直接用数组存储 i 能不能直接或间接到 j ,然后再对于每一个 b[i][j]==true 点将 fa[j]=fa[i] 。最后记录所有 fa[i]==i 的点就是光盘数了。

for(k=1;k<=n;k++)
	  for(i=1;i<=n;i++)
	    for(j=1;j<=n;j++)
			b[i][j]=b[i][j]|(b[i][k]&b[k][j]);
    for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
        if(b[i][j]==true) fa[j]=fa[i];
	for(i=1;i<=n;i++) if(fa[i]==i) s++;
	cout<<s;

问题 F: 烦人的幻灯片(slides)

对于所有的数字编号记录他所在的可能幻灯片数，和对于所有的幻灯片记录可能的数字编号及数量，然后遍历，只要找到一个幻灯片的可能数字编号只有一个那就把这两个匹配起来，并把所有该幻灯片可能的编号的可能的幻灯片数减减，若途中没有唯一匹配且数量还有剩，就无解了。

#include<bits/stdc++.h>
using namespace std;
int a[110][100],ans[100],f[100];
int an2[100];
int xmin[100],xmax[100],ymin[100],ymax[100];
bool b[501];
char s[100];
int main() {
	long n,m,i,j,k,x,y,l;
	bool bo,boo;
	memset(b,true,sizeof(b));
	cin>>n;
	for(i=1; i<=n; i++)
		cin>>xmin[i]>>xmax[i]>>ymin[i]>>ymax[i];
	for (i=1; i<=n; i++) {
		cin>>x>>y;
		for (j=1; j<=n; j++)
			if((x>=xmin[j])&&(x<=xmax[j])&&(y>=ymin[j])&&(y<=ymax[j])) {
				a[i][0]++;
				a[i][a[i][0]]=j;
				f[j]++;
			}
	}
	boo=true;
	for (k=1; k<=n; k++) {
		bo=false;
		for (i=1; i<=n; i++)
			if (b[i]==true) {
				for (j=1; j<=a[i][0]; j++)
					if (f[a[i][j]]==1) {
						for (l=1; l<=a[i][0]; l++) f[a[i][l]]--;
						bo=true;
						ans[i]=a[i][j];
						b[i]=false;
						break;
					}
				if (bo==true)  break;
				if (i==n) boo=false;
			}
		if(boo==false) break;
	}
	for (i=1; i<=n; i++) s[i]=i+64;
	if (boo==false)  cout<<"None";
	else {
		for(i=1; i<=n; i++)
			an2[ans[i]]=i;
		for(i=1; i<=n; i++) cout<<s[i]<<" "<<an2[i]<<endl;
	}
}

问题 G: 构造完全图

昨天同样的题问题D：走廊泼水节，注意数据范围有点不同。

#define N 200001

问题 H: Intervals

两种解法。

法一：差分约束系统

对于每一个 k-1 到 k 连权为 0 的边，每一个 k 到 k-1 连权为 0 的边，对于每一个 $a_{i}-1$ 到 $b_{i}$ 连权为? $c_{i}$ 的边，跑一遍最长路， $d\left [ \max_{i=1->n}\left \{ b_{i} \right \}\right ]$ 即为答案。

#include<bit/stdc++.h>
using namespace std;
const int N = 500006, M = 5000006;
int n, m, d[N];
int Head[N], Edge[M], Leng[M], Next[M], tot;
bool v[N];
inline void add(int x, int y, int z) {
	Edge[++tot] = y;
	Leng[tot] = z;
	Next[tot] = Head[x];
	Head[x] = tot;
}
void spfa() {
	queue<int> q;
	q.push(0);
	v[0] = 1;
	d[0] = 0;
	while (q.size()) {
		int x = q.front();
		q.pop();
		v[x] = 0;
		for (int i = Head[x]; i; i = Next[i]) {
			int y = Edge[i];
			if (d[y] < d[x] + Leng[i]) {
				d[y] = d[x] + Leng[i];
				if (!v[y]) {
					v[y] = 1;
					q.push(y);
				}
			}
		}
	}
}
int main() {
	memset(d, 0xcf, sizeof(d));
	tot = m = 0;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z);
		add(x, y + 1, z);
		m = max(m, y + 1);
	}
	for (int i = 1; i <= m; i++) {
		add(i - 1, i, 0);
		add(i, i - 1, -1);
	}
	spfa();
	cout << d[m] << endl;
	return 0;
}

法二：贪心加数据结构优化（数据结构优化不会，只会贪心，但可过）。

#include<bits/stdc++.h>
using namespace std;
struct S{
	int l,r,num;
}s[50004];
bool operator < (S x,S y){
	return x.r<y.r;
}
int n,ans;
int now[50004];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&s[i].l,&s[i].r,&s[i].num);
	}
	sort(s+1,s+n+1);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=ans;j++)
			if(now[j]>=s[i].l && now[j]<=s[i].r) s[i].num--;
		for(int j=1;j<=s[i].num;j++)
			now[++ans]=s[i].r-j+1;
	}
	cout<<ans;
}