SP211 PRIMIT - Primitivus recurencis（欧拉回路）

SP211 PRIMIT - Primitivus recurencis

欧拉回路

Warning: enormous Input/Output data

警告：巨大的输入/输出

经过若干（11）次提交后，我终于明白了，真的要把数组开大。

题意：给定 t 组数据，每组数据有n条有向边（对，没给范围），每个点的编号<=1000。

打印一串最短的数列包括所有有向边。

这是满足样例的一组解：(8, 5, 1, 4, 2, 3, 9, 6, 4, 5, 7, 6, 2, 8, 6)

分析样例发现，编号为2,4,8的3个点是奇点（此处指出度>入度的点）。而答案为15=12+3=边数+奇点数

我们就可以联想到欧拉回路。

你需要知道一件事：对于每个满足欧拉回路性质的图，不管你怎么走，总能一次性把所有边走一遍。（自寻死路不算qwq）

而满足样例的一组解可拆分为：(8, 5, 1, 4, 2, 3, 9, 6) (4, 5, 7, 6) (2, 8, 6)

显然走了3次，起点为8,4,2。

答案就十分显然了。

不，并没有结束。因为我们忽略了图的连通性和没有奇点的图。

对于没有奇点的图，显然我们要走一次，数列长度为 边数+1。

我们可以用dfs把以上情况一起处理掉。

注意dfs只需要把点遍历一遍，而不用遍历边（会T掉），原因见上↑

（这种冷门题没人看得见吧QAQ）

code：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

template <typename T> inline T max(T &a,T &b) {return a>b ?a:b;}

template <typename T> inline void read(T &x){

    char c=getchar(); x=;

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();

}

template <typename T> inline void output(T x){

    if(!x) {putchar(); return ;}

    int wt[],l=;

    while(x) wt[++l]=x%,x/=;

    while(l) putchar(wt[l--]+);

}

int t[],ans,mxd,n,tt,u,v,_top,st[];

int cnt,hd[],nxt[],ed[],poi[];//尽量开大

bool vis[],appear[];

inline void add(int x,int y){ //邻接表

    nxt[ed[x]]=++cnt; hd[x]= hd[x] ? hd[x]:cnt;

    ed[x]=cnt; poi[cnt]=y; ++t[x]; --t[y];

}

inline void dfs(int u){ //dfs遍历点

    vis[u]=;

    for(int i=hd[u];i;i=nxt[i])

        if(!vis[poi[i]])

            dfs(poi[i]);

}

int main(){

    scanf("%d",&tt);

    while(tt--){

        memset(appear,,sizeof(appear)); //该清空的都清空一遍

        memset(vis,,sizeof(vis));

        memset(t,,sizeof(t));

        memset(hd,,sizeof(hd));

        memset(nxt,,sizeof(nxt));

        memset(ed,,sizeof(ed));

        memset(poi,,sizeof(poi));

        read(n); ans=n; mxd=cnt=; //边数是固定的，可以提出来

        for(int i=;i<=n;++i){

            read(u); read(v);

            mxd=max(mxd,max(u,v));

            add(u,v);

            appear[u]=appear[v]=;

        }

        for(int i=;i<=mxd;++i) if(t[i]>) ans+=t[i],dfs(i); //有奇点的图

        for(int i=;i<=mxd;++i) if(!vis[i]&&appear[i]) dfs(i),++ans;  //没有奇点的图

        output(ans); putchar('\n');

    }return ;

}

巴特西

SP211 PRIMIT - Primitivus recurencis（欧拉回路）

最新文章

热门文章