hdu多校2C

题意:找多条路径覆盖所有的边,求最小路径数,要求输出路径

题解:新建一个点n+1,所有奇点向它连边,然后跑欧拉回路,最后把新加的边删去,一段连续的边就是一条路径

= =但是由于太久没写欧拉回路以及之前的板子有点问题,导致比赛时没做出来

还有一个坑点是,明明题目里说了没有重边,我规定不能访问父亲居然就wa了!!!!

//#pragma comment(linker, "/stack:200000000")

//#pragma GCC optimize("Ofast,no-stack-protector")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

//#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define pi acos(-1.0)

#define ll long long

#define vi vector<int>

#define mod 1000000007

#define ld long double

#define C 0.5772156649

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#define pll pair<ll,ll>

#define pil pair<int,ll>

#define pli pair<ll,int>

#define pii pair<int,int>

#define cd complex<double>

#define ull unsigned long long

#define base 1000000000000000000

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

#define fio ios::sync_with_stdio(false);cin.tie(0)

inline void add(ll &a,ll b){a+=b;if(a>=mod)a-=mod;}

inline void sub(ll &a,ll b){a-=b;if(a<0)a+=mod;}

inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

inline ll qp(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}

using namespace std;

const double eps=1e-8;

const ll INF=0x3f3f3f3f3f3f3f3f;

const int N=200000+10,maxn=400000+10,inf=0x3f3f3f3f;

struct edge{

    int to,Next,id;

}e[maxn];

int cur[N];

int cnt,head[N],deg[N];

vi s[N];

int res,n,m,sum;

bool ban[maxn];

inline void init()

{

    cnt=res=sum=0;

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

        head[i] = -1;

        deg[i] = 0;

    }

}

inline void add(int u,int v,int id)

{

    e[cnt].to=v;

    e[cnt].Next=head[u];

    e[cnt].id=id;

    ban[cnt] = false;

    head[u]=cnt++;

    e[cnt].to=u;

    e[cnt].Next=head[v];

    e[cnt].id=id;

    ban[cnt] = false;

    head[v]=cnt++;

}

void dfs(int u,int f)

{

//    cout << u << " " << f << endl;

//    for(int i=head[u];~i;i=e[i].Next)

    while(head[u] != -1)

    {

        int i = head[u];

        int x=e[i].to;

        head[u] = e[i].Next;

        if(!ban[e[i].id])

        {

            ban[e[i].id]=1;

            dfs(x,u);

            if(u!=n+1)

            {

                if(x!=n+1)

                {

                    s[res].pb(i&1?-e[i].id:e[i].id);

                }

                else

                {

                    if((int)s[res].size()!=0)res++;

                }

            }

        }

    }

}

int main()

{

    int a, b;

    while(~scanf("%d%d",&n, &m))

    {

        init();

        for(int i=1;i<=m;i++)

        {

            scanf("%d%d", &a, &b);

            add(a,b,i);

            deg[a]++,deg[b]++;

        }

        int te=m;

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

            if(deg[i]&1)

                add(i,n+1,++te);

        dfs(n+1,-1);

        if((int)s[res].size()!=0)res++;

            for(int i=1,j;i<=n;i++)

                while((j=head[i])!=-1){

                    head[i] = e[j].Next;

                    if(!ban[e[j].id])

                    {

                        dfs(i,-1);

                        if(s[res].size()!=0)res++;

                    }

                }

        printf("%d\n",res);

        for(int i=0;i<res;i++)

        {

            printf("%d",s[i].size());

            for(int j=s[i].size() - 1;j >= 0;--j)

                printf(" %d",s[i][j]);

            puts("");

            s[i].clear();

        }

//        for(int i = 1; i <= n; i++) printf("%d ", head[i]);

    }

    return 0;

}

/********************

6 6

1 2

2 3

3 4

2 5

3 5

2 6

6 6

1 2

2 3

1 3

4 5

5 6

4 6

31 36

12 28

12 27

27 28

15 26

15 25

25 26

17 23

17 24

23 24

20 21

20 22

21 22

29 30

30 31

29 31

1 2

2 3

3 4

1 4

4 5

4 6

5 7

6 7

7 8

8 9

9 10

10 11

11 12

10 14

14 15

10 13

13 16

16 17

13 18

18 19

19 20

8 7

1 2

2 3

3 4

4 8

5 6

6 7

7 4

********************/

巴特西

hdu多校2C

最新文章

热门文章