sgu 286. Ancient decoration（最小环覆盖）

给你一个n个点，每个点度为k（k为偶数）的无向图，问是否能将图中的n条边染色，使得每个点都拥有两条被染色的边。也就是说，是否存在拥有原图中n条边的子图，使得每个点的度为2？仔细想想，每个点的度为2，实际上就是求原图的最小环覆盖了。

求最小环覆盖的方法就是先求出原图的有向欧拉回路（k为偶数，欧拉回路必然存在），然后问题就转化成了是否能选择欧拉回路中的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;  
}

补充：软件开发 , C++ ,