在此处输入标题 2

列表项

未分类

G - 欧拉路

题目大意：欧拉回路模板题，从一个点出发经过每条边一次再回到起点。

解题思路：套用讲课的人的板子即可。

参考代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int top,du[50],Last[50],Next[4000],End[4000],stk[2005];
bool f[2005];

void _addside(int x,int y,int z){

    Next[z*2]=Last[x]; End[z*2]=y; Last[x]=z*2;
    Next[z*2+1]=Last[y]; End[z*2+1]=x; Last[y]=z*2+1;
    du[x]++;
    du[y]++;
}

void _euler(int e){

    int p,x=End[e],y;
    for(p=Last[x];p;p=Next[p]){
        if(f[p/2])continue;
        f[p/2]=1;
        _euler(p);
    }
    stk[++top]=e/2;
}


int main(){

    int x,y,z,m,i;
    End[1]=1;
    while(true){
        scanf("%d%d",&x,&y);
        if(x==0&&y==0)break;
        memset(Last,0,sizeof(Last));
        memset(du,0,sizeof(du));
        m=1;
        scanf("%d",&z);
        _addside(x,y,z);
        while(true){
            scanf("%d%d",&x,&y);
            if(x==0&&y==0)break;
            scanf("%d",&z);
            _addside(x,y,z);
        }
        for(i=1;i<=44;i++)
            if(du[i]&1)break;
        if(i<=44){
            puts("Round trip does not exist.");
            continue;
        }
        top=0;
        memset(f,0,sizeof(f));
        _euler(1);
        if(top<=m)puts("Round trip does not exist.");
        else{
            for(i=1;i<top;i++)
                printf("%d ",stk[i]);
            putchar(10);
        }
    }
    return 0;
}

H - 拓扑排序

题目大意：依次给出一些数的大小关系，询问【关系是否矛盾】【是否有唯一升序】，并输出在给出第几条大小关系时能得出结论。

解题思路：拓扑排序模板题，相对于一般模板题的变化在于需要输出在给出第几条信息时能得出【唯一升序】或【矛盾】的结论。那么每新加入一条边就跑一次拓扑排序即可。
(ps：二分答案应该也可以。)

参考代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int ans[30],du[30],e[30],stk[30],n;
char ch[2005][5];

vector<int>g[30];

int _check(){

    int top=0,i,tim=0,u;
    bool flag=false;
    memcpy(e,du,sizeof(e));
    for(i=1;i<=n;i++)
        if(e[i]==0)stk[++top]=i;
    if(top>=2)flag=true;

    while(top){
        ans[++tim]=u=stk[top--];
        for(i=0;i<g[u].size();i++){
            e[g[u][i]]--;
            if(e[g[u][i]]==0)stk[++top]=g[u][i];
        }
        if(top>=2)flag=true;
    }
    if(tim==n){
        if(flag)return -1;
        return 1;
    }
    return 0;
}




int main(){

    int m,i,x,y,a;
    while(1){

        scanf("%d%d",&n,&m);
        if(n+m==0)break;
        for(i=1;i<=n;i++){
            g[i].clear();
            du[i]=0;
        }
        for(i=1;i<=m;i++)
            scanf("%s",ch[i]);
        for(i=1;i<=m;i++){
            x=ch[i][0]-64;
            y=ch[i][2]-64;
            g[x].push_back(y);
            du[y]++;
            a=_check();
            if(a>=0)break;
        }
        if(a==1){
            printf("Sorted sequence determined after %d relations: ",i);
            for(i=1;i<=n;i++)
                printf("%c",ans[i]+64);
            printf(".\n");
        }
        else if(a==0)
            printf("Inconsistency found after %d relations.\n",i);
        else printf("Sorted sequence cannot be determined.\n");
    }
    return 0;
}

I - 并查集

题目大意：并查集模板题，询问某个集合里有多少个元素。

解题思路：我不会并查集……

参考代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int fa[40000],sz[40000];

int _getfa(int x){

    if(x==fa[x])return x;
    return fa[x]=_getfa(fa[x]);

}


int main(){

    int n,m,i,k,x,y;
    while(true){

        scanf("%d%d",&n,&m);
        if(n+m==0)break;
        for(i=0;i<=n;i++){
            fa[i]=i;
            sz[i]=1;
        }
        for(i=1;i<=m;i++){
            scanf("%d",&k);
            x=-1;
            while(k--){
                scanf("%d",&y);
                if(x>=0){
                    x=_getfa(x);
                    y=_getfa(y);
                    if(x==y)continue;
                    sz[y]+=sz[x];
                    fa[x]=y;
                }
                x=y;
            }
        }
        printf("%d\n",sz[_getfa(0)]);
    }
    return 0;
}