T1: 题目描述: 关于回路的问题一直是计算机科学届的热门话题，比较典型的就有哈密尔顿 (Hamilton)回路和欧拉(Euler)回路。 设 G 是一个简单无向图，一个经过 G 的全部顶点的回路称为 G 的哈密尔顿 回路，已经证明哈密尔顿回路问题是一个 NPC(Non-deterministic Polynomial Complete)问题，相形之下，欧拉回路则要简单的多，一个经典结论是“一个无 向图存在欧拉回路，当且仅当该图所有顶点度数都是偶数”。 我们的问题很简单，给定一个N个点，M条边的无向图(点标号为 1 到N)，问 这个无向图是否恰好是一个环。所谓的环由K个互异的点V1，V2，V3，…，VK（K 至少为 3）组成，并且在V1与V2，V2与V3，…，VK与V1间有边相连，而没有多余 的其他边。 【输入输出样例 1】 3 3 1 2 2 3 1 3 YES 【输入输出样例 1 说明】 给定的图恰为一个 3 个顶点的环。 【输入输出样例 2】 4 4 1 2 2 3 3 1 1 4 NO 【输入输出样例 2 说明】 虽然给定的图包含一个 3 个顶点的环，但不符合整个图恰为一个环的条件。
数据范围: 100%的数据中，1 ≤ N ≤ 10，1 ≤ M ≤ 20。
分析: 首先看题,发现是一道很简单的欧拉回路题目,O(∩_∩)O,心中窃喜,结果一看数据范围,看不懂的小,纠结了半天,也没想到什么算法让数据最大只有20,只有打了一个欧拉回路.结果居然A了,orz,真是迷啊! code:
#include<iostream>#include<algorithm>#include<cstdio>#include<cstdlib>#include<cstring>using namespace std;void setIO(const string&a) { freopen((a+".in").c_str(),"r",stdin); freopen((a+".out").c_str(),"w",stdout);}#include<vector>vector<int> G[15];int cnt=0,head,tail;int n,m;bool dfs(int u,int PRe) { int next=0; for(unsigned i=0;i<G[u].size();i++) { cnt++; int v=G[u][i]; if(v==pre) continue; if(pre) { if(!next) next=v; else if(next!=v) return 0; }else { if(!next) next=v; else if(!tail) tail=v; else return 0; } } if(u==tail) return next==head&&cnt==m*2; return dfs(next,u);}int main() { setIO("circuit"); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); G[u].push_back(v); G[v].push_back(u); } for(int i=1;i<=n;i++) { if(G[i].size()) { head=i; printf("%s/n",dfs(i,0)?"YES":"NO"); return 0; } }}T2: 题目描述: 【问题描述】 有N个三维空间上的点(Xi，Yi，Zi)。我们定义三维空间上两个点的艾格佩因 距离为 
现在，我们为这 N 个点两两之间连了一条长度为他们的艾格佩因距离的无向 边，得到一个完全图，现在我们想知道这个完全图的最小生成树的边权和。 【输入文件】 输入文件 space.in 的第一行为一个正整数 N。 接下来N行每行三个数Xi，Yi，Zi表示第i个点的坐标。 【输出文件】 输出文件 space.out 包含一个整数即最小生成树的边权和。 样例及数据范围:
分析: 刚拿到这题发现是一道MST的模板题,但是看到是一张完全图且n最大是1e5,所以我们肯定不能把所有的边都求出来,那么考虑删边,一开始我以为从他定义的距离考虑,后来发现不行,那么这题可以转化成从(n^2-1)条边中选择(n-1)条边的问题.此时我们可以考虑给x,y,z排序,然后建边,用kruskal求解. 解法的证明: 我们需要满足每辆个点有且仅有一条边,所以我们排序后选择每两个相邻的点之间的距离,因为若中间相隔必然没有相邻优.而对于这样是否能建成一个树也是很显然的.因为相邻两点必然两两不同,所以一定会有树.至于排三次序后出现环的话,可以用并查集解决.
Code:
#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#include<cstdlib>#include<queue>#define fo(i,a,b) for(int i=a;i<=b;i++)#define fod(i,a,b) for(int i=a;i>=b;i--)using namespace std;const int MAXN=300000+10;struct ex{ int x,id; bool Operator < (const ex &a){ return a.x>x; }}ex[MAXN];struct ey{ int y,id; bool operator < (const ey &a){ return a.y>y; }}ey[MAXN];struct ez{ int z,id; bool operator < (const ez &a){ return a.z>z; }}ez[MAXN];int n,fa[MAXN];int find(int x){ return fa[x]==x?fa[x]:fa[x]=find(fa[x]);}struct edge{ int from,to,val; edge(int from=0,int to=0,int val=0):from(from),to(to),val(val){}}e[MAXN*2];bool cmp(const edge &a,const edge& b){ return a.val<b.val;}int len=0;void kruskal(){ long long ans=0; fo(i,1,len){ int u=e[i].from,v=e[i].to; int x=find(u),y=find(v); if(x==y) continue; else{ ans+=e[i].val; fa[x]=y; } } printf("%d",ans);}int main(){ freopen("space.in","r",stdin); freopen("space.out","w",stdout); scanf("%d",&n); fo(i,1,n){ fa[i]=i; ex[i].id=i; ey[i].id=i; ez[i].id=i; scanf("%d%d%d",&ex[i].x,&ey[i].y,&ez[i].z); } sort(ex+1,ex+1+n); sort(ey+1,ey+1+n); sort(ez+1,ez+1+n); fo(i,2,n){ e[++len]=edge(ex[i-1].id,ex[i].id,abs(ex[i].x-ex[i-1].x)); e[++len]=edge(ey[i-1].id,ey[i].id,abs(ey[i].y-ey[i-1].y)); e[++len]=edge(ez[i-1].id,ez[i].id,abs(ez[i].z-ez[i-1].z)); } sort(e+1,e+1+len,cmp); kruskal(); return 0;}T3 还没改完 continue—–
新闻热点
疑难解答
