http://acm.sgu.ru/problem.php?contest=0&problem=286
先找欧拉回路，再做二分匹配，输出匹配
有一道题和这个很像：HDU 3551 Hard Problem(带花树匹配)
但是这道题用带花树内存开不下匹配的数组。。。
1 /** 2 *先找欧拉回路，再做二分匹配，输出匹配 3 *场上想的是用带花树做，因为之前做过一道类似的题：HDU 3551 Hard Problem 4 *设边e(u,v)，则将(u,e) (v,e') (e,e')连起来 5 *注意u有deg[u]-D[u]-1个顶点，v同样，e,e'表示将边e拆成e和e'两个顶点 6 *然后用带花树算法做匹配，如果有完美匹配则输出YES，并输出匹配，否则输出NO。 7 *但是这种做法做匹配数组开不下。。。(90000*90000的。。。) 8 * 9 *@Author: xysmlx xiaohai 10 */ 11 //#pragma comment(linker, "/STACK:102400000,102400000") 12 #include<cstdio> 13 #include<iostream> 14 #include<cstring> 15 #include<string> 16 #include<cmath> 17 #include<set> 18 #include<list> 19 #include<map> 20 #include<iterator> 21 #include<cstdlib> 22 #include<vector> 23 #include<queue> 24 #include<stack> 25 #include<algorithm> 26 #include<functional> 27 using namespace std; 28 typedef long long LL; 29 #define ROUND(x) round(x) 30 #define FLOOR(x) floor(x) 31 #define CEIL(x) ceil(x) 32 const int maxn=510; 33 const int inf=0x3f3f3f3f; 34 const LL inf64=0x3f3f3f3f3f3f3f3fLL; 35 const double INF=1e30; 36 const double eps=1e-6; 37 int n,m,k; 38 int no[maxn][maxn]; 39 int deg[maxn]; 40 41 /** 42 *大数据二分图匹配：Hopcroft-Karp($O(sqrt{v}E)$) 43 *适用于数据较大的二分匹配(从0到n-1) 44 *输入：Nx,Ny,g[][] 45 *输出：res=MaxMatch();Mx[]My[] 46 */ 47 //const int maxn=0; 48 //const int inf=0x3f3f3f3f; 49 int g[maxn][maxn],Mx[maxn],My[maxn],Nx,Ny; 50 int dx[maxn],dy[maxn],dis; 51 bool vst[maxn]; 52 bool searchP() 53 { 54 queue<int>Q; 55 dis=inf; 56 memset(dx,-1,sizeof(dx)); 57 memset(dy,-1,sizeof(dy)); 58 for(int i=0; i<Nx; i++) 59 if(Mx[i]==-1) 60 { 61 Q.push(i); 62 dx[i]=0; 63 } 64 while(!Q.empty()) 65 { 66 int u=Q.front(); 67 Q.pop(); 68 if(dx[u]>dis) break; 69 for(int v=0; v<Ny; v++) 70 if(g[u][v]&&dy[v]==-1) 71 { 72 dy[v]=dx[u]+1; 73 if(My[v]==-1) dis=dy[v]; 74 else 75 { 76 dx[My[v]]=dy[v]+1; 77 Q.push(My[v]); 78 } 79 } 80 } 81 return dis!=inf; 82 } 83 bool DFS(int u) 84 { 85 for(int v=0; v<Ny; v++) 86 if(!vst[v]&&g[u][v]&&dy[v]==dx[u]+1) 87 { 88 vst[v]=1; 89 if(My[v]!=-1&&dy[v]==dis) continue; 90 if(My[v]==-1||DFS(My[v])) 91 { 92 My[v]=u; 93 Mx[u]=v; 94 return 1; 95 } 96 } 97 return 0; 98 } 99 int MaxMatch() 100 { 101 int res=0; 102 memset(Mx,-1,sizeof(Mx)); 103 memset(My,-1,sizeof(My)); 104 while(searchP()) 105 { 106 memset(vst,0,sizeof(vst)); 107 for(int i=0; i<Nx; i++) 108 if(Mx[i]==-1&&DFS(i)) res++; 109 } 110 return res; 111 } 112 113 /** 114 *Euler 路径(未知复杂度) 115 *首先计算出每个点的度数degree，然后调用euler函数，返回值为欧拉路径长度 116 *输入：n,g[][](邻接矩阵),deg[] 117 *输出：euler(),在相应地方处理 118 */ 119 void euler() 120 { 121 for(int i=0; i<n; i++) 122 { 123 if(deg[i]) 124 { 125 int u=i; 126 while(1) 127 { 128 for(int j=0; j<n; j++) 129 { 130 if(g[u][j]&&g[j][u]) 131 { 132 g[j][u]=0;///欧拉路径的边，在这里处理 133 deg[u]--,deg[i]--; 134 u=j; 135 break; 136 } 137 } 138 if(u==i) break; 139 } 140 } 141 } 142 } 143 144 void init() 145 { 146 memset(g,0,sizeof(g)); 147 memset(no,0,sizeof(no)); 148 memset(deg,0,sizeof(deg)); 149 Nx=n; 150 Ny=n; 151 m=n*k/2; 152 } 153 void input() 154 { 155 for(int i=1; i<=m; i++) 156 { 157 int u,v; 158 scanf("%d%d",&u,&v); 159 --u,--v; 160 g[u][v]=g[v][u]=1; 161 no[u][v]=no[v][u]=i; 162 deg[v]++,deg[u]++; 163 } 164 } 165 void solve() 166 { 167 euler(); 168 169 int ret=MaxMatch(); 170 if(ret<n) 171 { 172 puts("NO"); 173 return; 174 } 175 puts("YES"); 176 for(int i=0;i<n;i++) 177 printf("%d ",no[Mx[i]][i]); 178 } 179 int main() 180 { 181 // std::ios_base::sync_with_stdio(false); 182 // freopen("in.cpp","r",stdin); 183 scanf("%d%d",&n,&k); 184 init(); 185 input(); 186 solve(); 187 return 0; 188 }