很久没做题,水平不行了,bestcoder上的rating更是低的惨烈。这段时间开始坚持每个星期做一场比赛。
hdu5422 Rikka with Graph
这题不说了……
#include<stdio.h> #include<string.h> int n,m; int main() { int i,j; int u,v; while(~scanf("%d%d",&n,&m)) { bool flag=0; for(i=1;i<=m;i++) { scanf("%d%d",&u,&v); if((u==1 && v==n) || (u==n && v==1)) flag=1; } if(flag) printf("1 %d\n",n*(n-1)/2); else printf("1 1\n"); } return 0; }
hdu5423 Rikka with Tree
只有树是如下形态时才符合要求:最底层可以有多个结点,其余每层只能有一个结点。
#include<stdio.h> #include<string.h> #include<queue> using namespace std; int n; typedef struct Edge{ int to,next; }Edge; Edge edge[2010]; int head[1010],cnt; int d[1010]; typedef struct Node{ int x,dep,f; }Node; queue<Node> q; void add(int u,int v) { edge[cnt].to=v;edge[cnt].next=head[u]; head[u]=cnt++; return; } void bfs() { int i; while(!q.empty()) q.pop(); Node root; root.x=1;root.dep=1;root.f=0; memset(d,0,sizeof(d)); q.push(root); while(!q.empty()) { Node tmp=q.front();q.pop(); int u=tmp.x; int dep=tmp.dep; int f=tmp.f; d[dep]+=1; for(i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(v==f) continue; Node xh; xh.x=v;xh.f=u;xh.dep=dep+1; q.push(xh); } } return; } int main() { int i,j; while(~scanf("%d",&n)) { int u,v; cnt=0;memset(head,-1,sizeof(head)); memset(d,0,sizeof(d)); for(i=1;i<=n-1;i++) { scanf("%d%d",&u,&v); add(u,v); add(v,u); } bool flag=1; bfs(); for(i=1;i<=n;i++) { if(d[i]>=2 && d[i+1]>0) {flag=0;break;} } printf("%s\n",flag?"YES":"NO"); } return 0; }
hdu5424 Rikka with Graph II
好久没做bestcoder,我又忘了最后15分钟是hack时间,不能提交。结果在办公室一边做题一边吃吃喝喝,错过了提交时间。。
当时我的心情是这样的:
题意:n个顶点n条边,求是否存在哈密顿路。
我是这样做的:
if(不连通)//记录自环和重边数即可,不用遍历 NO else { if(没有环) { if(度=1的点超过2个) NO else YES } else { if(度=1的点超过2个) NO else if(度=1的点少于2个) YES else { 设这两个度为1的点为u,v 那么从这两个度为1的点迭代到环中,判断环上的这两个点是否有边相连?是:YES,否:NO } } }
其实代表了几种情况,画下图就明白了。具体见代码
#include<stdio.h> #include<string.h> int n; int d[1010][1010],du[1010]; typedef struct Edge{ int to,next; }Edge; Edge edge[2010]; int head[1010],cn; void add(int u,int v) { edge[cn].to=v;edge[cn].next=head[u]; head[u]=cn++; return; } int main() { int i,j; int u,v; while(~scanf("%d",&n)) { int cnt=0; memset(du,0,sizeof(du)); memset(d,0,sizeof(d)); cn=0;memset(head,-1,sizeof(head)); for(i=1;i<=n;i++) d[i][i]=1; for(i=1;i<=n;i++) { scanf("%d%d",&u,&v); if(u==v || d[u][v]) {cnt++;continue;} d[u][v]=1;d[v][u]=1; add(u,v);add(v,u); du[u]++;du[v]++; } if(cnt>=2) {printf("NO\n");continue;} int cc=0; for(i=1;i<=n;i++) if(du[i]==1) cc++; if(cnt==1) { if(cc>2) printf("NO\n"); else printf("YES\n"); continue; } if(cc>2) {printf("NO\n");continue;} if(cc<=1) {printf("YES\n");continue;} u=0; for(i=1;i<=n;i++) if(du[i]==1) { if(!u) u=i; else v=i; } int f=u; while(du[u]<3) { j=u; for(j=head[j];j!=-1;j=edge[j].next) { if(edge[j].to!=f) {f=u;u=edge[j].to;break;} } } f=v; while(du[v]<3) { j=v; for(j=head[j];j!=-1;j=edge[j].next) { if(edge[j].to!=f) {f=v;v=edge[j].to;break;} } } if((u==v) || !d[u][v]) printf("NO\n"); else printf("YES\n"); } return 0; }
hdu5425 Rikka with Tree II
这题比赛时候没做。。