是一题（一笔画）欧拉路的模板。欧拉路 是指若从起点到终点的路径恰经过图中每条边一次，则该路径成为欧拉路。存在欧拉路的条件是：图是联通的，且有0个或2个奇点（出入度为奇数的点）。欧拉路一定是从一个奇点开始，到另一个奇点结束，所以有两个奇点的时候能一笔画完。

若每多出两个奇点，画的次数就会+1，所以答案就是 奇点的个数 / 2。

//当一个无向图的奇点数为0或者2的时候
//可以不重边的走完所有点
//奇点为度为奇数的点
//所以一幅图要（奇点数/2）笔画完
#include <iostream>
using namespace std;
int du[1005];//统计一个点的度数
int main(){
	int n,m; cin>>n>>m;
	for(int i=1;i<=m;i++){
		int s,e;
		cin>>s>>e;
		du[s]++;
		du[e]++;
		//无向图，所以出入度相等
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		if(du[i]%2)
		ans++;
		if(ans==0) cout<<"1";//小特判
		else cout<<ans/2;
		return 0;
}

T2 合根植物（并查集）

是一道并查集的板子题，需要路径压缩。

#include <iostream>
using namespace std;
int n,m,k;
int f[1000005];
void init(){
	for(int i=1;i<=1000000;i++)
	f[i]=i;
	return;
}//初始化是必须的
int getf(int v){
	if(f[v]==v)
	return v;//查找根节点
	else{
		f[v]=getf(f[v]);
		return f[v];//路径压缩
	}
}//查找
void merge(int a,int b){
	int b1,b2;
	b1=getf(a);
	b2=getf(b);
	if(b1!=b2){
		f[b2]=b1;
		//左靠原则
	}
	return;
}//合并
int main(){
	cin>>n>>m>>k;
	//n为行数，m为列数
	init();
	for(int i=1;i<=k;i++){
		int x,y;
		cin>>x>>y;
		merge(x,y);
	}
	int sum=0;
	int tot=n*m;
	for(int i=1;i<=tot;i++){
		if(f[i]==i)
		sum++;
	}
	cout<<sum;
	return 0;
}

T3 奶酪

题目可以用dfs进行n^2的遍历，通过两点球心距离和两球半径之和的孰大孰小判断两球是相交，相切还是相离。

#include <iostream>
#include <cmath>
#include <cstring>
#include <stdio.h>
using namespace std;
long long int t,n,h,r;
bool vis[1005],found;
struct ball{
	int x,y,z;
}p[1004];
bool link(ball a,ball b){
	long long int dis=(pow(a.x-b.x,2)+pow(a.y-b.y,2)+pow(a.z-b.z,2));
	//两点距离的平方与2r的平方对比
	if(dis>4*r*r) 
		return false;
	else return true;//如果相交
}
void dfs(int a){
	if(found==true) return;
	if(p[a].z+r>=h){
		found=true;
		return;
	}
	for(int i=1;i<=n;i++){
		if(vis[i]==true) continue;
		else{
			if(link(p[a],p[i])){
				vis[i]=true;
				dfs(i);
			}//如果相交
		}
	}
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	cin>>t;
	while(t--){
		found = false;
		memset(vis,false,sizeof(vis));
		//初始化
		cin>>n>>h>>r;
		for(int i=1;i<=n;i++){
			cin>>p[i].x>>p[i].y>>p[i].z;
		}
		for(int i=1;i<=n;i++){
			if(p[i].z<=r){
				dfs(i);
				//如果和底边相交或相切
			}
		}
		if(found==true) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
}

T4 灾后重建（最短路）

用了动态规划的思想，是一道很好的练习floyd的题。

#include <iostream>
#include <stdio.h>
using namespace std;
const int inf=1e9+5;
int map[205][205];
int n,m,q,t[205];
int st,ed,v;//临时变量
void init(){
	for(int i=0;i<n;i++)
		for(int l=0;l<n;l++){
		map[i][l]=inf;
	}
	for(int i=0;i<n;i++) map[i][i]=0;
}//初始化
void updata(int x){
	for(int i=0;i<n;i++){
		for(int l=0;l<n;l++){
			map[i][l]=min(map[i][l], map[i][x]+map[x][l]);
		}
	}
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	cin>>n>>m;
	init();
	for(int i=0;i<n;i++) cin>>t[i];
	for(int i=0;i<m;i++){
		cin>>st>>ed>>v;
		map[st][ed]=v;
		map[ed][st]=v;
		//存图
	}
	cin>>q;
	int cur=0;
	while(q--){
		cin>>st>>ed>>v;
		while(t[cur]<=v&&cur<n){
			updata(cur);
			cur++;//时间是逐渐变大的，所以已经做过中转的村庄不会再用到
		}
		if(t[st]>v||t[ed]>v||map[st][ed]==inf) cout<<"-1"<<endl;
		else cout<<map[st][ed]<<endl;
	}
	return 0;
}

T5 聪明的猴子

生成树的模板题。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
struct edge{
	int s,e;
	long long int v;
}p[1000005];
int f[1005];
int x[1005],y[1005];
int M,mk[505],n;
int ans;
int cnt;
int getf(int x){
	if(f[x]==x) return x;
	else{
		f[x]=getf(f[x]);
		return f[x];
	}
}
bool merge(int x,int y){
	int x1,y1;
	x1=getf(x);
	y1=getf(y);
	if(x1!=y1){
		f[x1]=y1;
		return true;
	}
	return false;//已经联通
}
void init(){
	for(int i=1;i<=n;i++){
		f[i]=i;
	}
	return;
}
long long int len(int x1,int y1,int x2,int y2){
	return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);//返回距离的平方
}
bool cmp(edge a,edge b){
	return a.v<b.v;
}
int main(){
	cin>>M;
	for(int i=1;i<=M;i++){
		int aa; cin>>aa;
		mk[i]=aa*aa;
	}
	sort(mk+1,mk+1+M);
	cin>>n;
	init();
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
	}//读入数据
	for(int i=1;i<=n;i++){
		for(int l=i+1;l<=n;l++){
			long long int lens;
			lens=len(x[i],y[i],x[l],y[l]);
			cnt++;
			p[cnt].s=i;
			p[cnt].e=l;
			p[cnt].v=lens;
			//读入所有边
		}
	}
	int time=n*(n-1)/2;
	sort(p+1,p+1+time,cmp);//对time条边进行排序
	cnt=0;
	long long int max=0;
	for(int i=1;i<=time;i++){
		if(merge(p[i].s,p[i].e)){
			cnt++;
			max=p[i].v;
		}
		if(cnt==time-1) break;
	}
	for(int i=M;i>=1;i--){
		if(mk[i]>=max) ans++;
		else break;
	}
	cout<<ans;
	return 0;
}

下附代码：

#include <bits/stdc++.h>
using namespace std;
const int maxx=1e6+5;
int n,m;
int vis[maxx];
vector<int> book[maxx];
queue<int> b;
void dfs(int x){
	if(vis[x]==1) return;
	vis[x]=1;
	cout<<x<<' ';
	for(int i=0;i<book[x].size();++i){
		dfs(book[x][i]);
	}
}
void bfs(){
	b.push(1);
	while(!b.empty()){
		int x=b.front();
		b.pop();
		cout<<x<<' ';
		vis[x]=1;
		for(int i=0;i<book[x].size();++i){
			int next=book[x][i];
			if(vis[next]==1) continue;
			else{
				b.push(next);
				vis[next]=1;
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int f,e;
		cin>>f>>e;
		book[f].push_back(e);
	}
	for(int i=1;i<=n;i++){
		sort(book[i].begin(),book[i].end());
	}//排序n种资料
	dfs(1);
	cout<<endl;
	memset(vis,0,sizeof(vis));
	bfs();
	return 0;
}

T2 Floyd（最短路n^3模板题）

floyd比较短，本质上是一种dp算法。时间复杂度为 n^3，n<10^3内的数据可以用。floyd适用性也很高，遍历所有点所以可以做到一些生成树算法的功能。

下附代码：

#include <iostream>
#include <cstring>
using namespace std;
const long long int mod = 998244354;
const long long int INF=25e13+500;
int n,m;
long long int ans;
long long int map[505][505];
int main(){
	for(int i=1;i<=503;i++)
	for(int l=1;l<=503;l++){
		if(i==l) map[i][l]=0;
		else map[i][l]=INF;
	}
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int s,e,v;
		cin>>s>>e>>v;
		if(map[s][e]!=0&&map[s][e]>v){
			map[s][e]=v;
			map[e][s]=v;
		}
		//无向图。
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int l=1;l<=n;l++){
				if(i==l) continue;
				if(map[k][l]<INF&&map[i][k]<INF&&map[i][l]>(map[k][l]+map[i][k]))
				map[i][l]=(map[k][l]+map[i][k]);
			}
		}
	}
	for(int i=1;i<=n;i++){
		ans=0;
		for(int l=1;l<=n;l++){
			ans+=map[i][l];
			ans%=mod;
		}
		cout<<ans%mod<<endl;
	}
	return 0;
}

T3 单源最短路径（标准版）

用dijkstra时要用堆来优化缩边过程的选点步骤，可以用优先队列来存放到各点的估计值。

各种存图方式，代码用了vector数组进行存图

下附代码：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int inf=2e9+5;
struct point{
	int end,len;
	bool operator < (const point a) const{
		return len < a.len;
	}//重载运算符
	bool operator > (const point a) const{
		return len > a.len;
	}
};
int n,m,st,cnt,now;
bool book[100005];
vector <point> a[100005];//最多1e5个点
priority_queue <point, vector<point>,greater<point> > dis;
int ans[100005];//存答案的数组。
int main(){
	cin>>n>>m>>st;
	for(int i=1;i<=100005;i++){
		ans[i]=inf;
	}
	ans[st]=0;
	for(int i=1;i<=m;i++){
		int s,e,v;
		cin>>s>>e>>v;
		a[s].push_back({e,v});
	}//vector存图
	dis.push({st,0});//存入起点
	while(!dis.empty()){
		point temp=dis.top();
		dis.pop();
		now=temp.end;
		//因为确定值不能重复更新（优先队列内仍可能存在
		//所以要加一个判断。
		if(!book[now]){
			book[now]=true;
			for(int i=0;i<a[now].size();i++){
				//遍历所有边 vector下标从0开始
				point x=a[now][i];
				int to=x.end;
				int v=x.len;
				//dijkstra核心代码
				if(ans[to]>ans[now]+v){
					ans[to]=ans[now]+v;
				//dijkstra核心代码
					if(!book[to]){
						//减少判断次数，去掉不影响算法正确性。
						dis.push({to,ans[to]});
					}
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<' ';
	}
	return 0;
}