很久没做题，水平不行了，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
这题比赛时候没做。。