給你一個(gè)n個(gè)點(diǎn)，每個(gè)點(diǎn)度為k（k為偶數(shù)）的無(wú)向圖，問(wèn)是否能將圖中的n條邊染色，使得每個(gè)點(diǎn)都擁有兩條被染色的邊。也就是說(shuō)，是否存在擁有原圖中n條邊的子圖，使得每個(gè)點(diǎn)的度為2？仔細(xì)想想，每個(gè)點(diǎn)的度為2，實(shí)際上就是求原圖的最小環(huán)覆蓋了。

求最小環(huán)覆蓋的方法就是先求出原圖的有向歐拉回路（k為偶數(shù)，歐拉回路必然存在），然后問(wèn)題就轉(zhuǎn)化成了是否能選擇歐拉回路中的n條邊，使得所有點(diǎn)都被覆蓋？這不就轉(zhuǎn)化成了DAG的最小路徑覆蓋了么！

?

    #include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<fstream>

#include<sstream>

#include<bitset>

#include<vector>

#include<string>

#include<cstdio>

#include<cmath>

#include<stack>

#include<queue>

#include<stack>

#include<map>

#include<set>

#define FF(i, a, b) for(int i=a; i<b; i++)

#define FD(i, a, b) for(int i=a; i>=b; i--)

#define REP(i, n) for(int i=0; i<n; i++)

#define CLR(a, b) memset(a, b, sizeof(a))

#define debug puts("**debug**")

#define LL long long

#define PB push_back

using namespace std;



const int maxn = 1001;

int g[maxn][maxn], degree[maxn], match[maxn], id[maxn][maxn];

bool vis[maxn];

int n, k, u, v;



void Euler()

{

    FF(i, 1, n+1) if(degree[i])

    {

        int u = i;

        while(true)

        {

            FF(j, 1, n+1) if(g[u][j] && g[j][u])

            {

                g[j][u] = 0;

                degree[u]--, degree[i]--;

                u = j;

                break;

            }

            if(u == i) break;

        }

    }

}



bool dfs(int u)

{

    FF(i, 1, n+1) if(!vis[i] && g[u][i])

    {

        vis[i] = true;

        if(match[i] == 0 || dfs(match[i]))

        {

            match[i] = u;

            return true;

        }

    }

    return false;

}



bool max_match()

{

    CLR(match, 0);

    FF(i, 1, n+1)

    {

        CLR(vis, 0);

        if(!dfs(i)) return false;

    }

    return true;

}



int main()

{

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

    {

        CLR(degree, 0);CLR(g, 0);

        REP(i, n*k/2)

        {

            scanf("%d%d", &u, &v);

            g[u][v] = g[v][u] = 1;

            id[u][v] = id[v][u] = i+1;

            degree[u]++, degree[v]++;

        }

        Euler();

        if(max_match())

        {

            puts("YES");

            FF(i, 1, n+1) printf("%d\n", id[match[i]][i]);

        }

        else puts("NO");

    }

    return 0;

}


  

?

?

sgu 286. Ancient decoration（最小環(huán)覆蓋）