http://acm.hdu.edu.cn/showproblem.php?pid=3551
终于把带花树专题刷完了
题意：
给定一个无向图，问能否删除一些边使得所有顶点的读数为给定的度数
方法：
这道题看网上有用网络流解的，这里用带花树做匹配来解。
先预处理所有的顶点的度数deg，然后与给定的度数D比较。
设边e(u,v)，则将(u,e) (v,e') (e,e')连起来，注意u有deg[u]-D[u]-1个顶点，v同样，e,e'表示将边e拆成e和e'两个顶点，然后用带花树算法做匹配，如果有完美匹配则输出YES，否则输出NO。（想一下，如果有完美匹配就表明这些多余的边能够直接移走使每个顶点的度数变为D）
注意：
重边时拆分顶点的编号唯一（这里WA了好多次。。。）；特判D[i]>deg[i]的情况
1 //#pragma comment(linker, "/STACK:102400000,102400000") 2 #include<cstdio> 3 #include<iostream> 4 #include<cstring> 5 #include<string> 6 #include<cmath> 7 #include<set> 8 #include<list> 9 #include<map> 10 #include<iterator> 11 #include<cstdlib> 12 #include<vector> 13 #include<queue> 14 #include<stack> 15 #include<algorithm> 16 #include<functional> 17 using namespace std; 18 typedef long long LL; 19 #define ROUND(x) round(x) 20 #define FLOOR(x) floor(x) 21 #define CEIL(x) ceil(x) 22 const int maxn=1010; 23 const int inf=0x3f3f3f3f; 24 const LL inf64=0x3f3f3f3f3f3f3f3fLL; 25 const double INF=1e30; 26 const double eps=1e-6; 27 /** 28 *一般图的最大基数匹配：带花树算法 29 *输入：g[][],n(输入从0到n-1,用addEdge()加边) 30 *输出：gao()(最大匹配数),match[](匹配) 31 */ 32 //const int maxn=0; 33 struct Matching 34 { 35 deque<int> Q; 36 int n; 37 //g[i][j]存放关系图：i,j是否有边,match[i]存放i所匹配的点 38 bool g[maxn][maxn],inque[maxn],inblossom[maxn],inpath[maxn]; 39 int match[maxn],pre[maxn],base[maxn]; 40 41 //找公共祖先 42 int findancestor(int u,int v) 43 { 44 memset(inpath,0,sizeof(inpath)); 45 while(1) 46 { 47 u=base[u]; 48 inpath[u]=true; 49 if(match[u]==-1)break; 50 u=pre[match[u]]; 51 } 52 while(1) 53 { 54 v=base[v]; 55 if(inpath[v])return v; 56 v=pre[match[v]]; 57 } 58 } 59 60 //压缩花 61 void reset(int u,int anc) 62 { 63 while(u!=anc) 64 { 65 int v=match[u]; 66 inblossom[base[u]]=1; 67 inblossom[base[v]]=1; 68 v=pre[v]; 69 if(base[v]!=anc)pre[v]=match[u]; 70 u=v; 71 } 72 } 73 74 void contract(int u,int v,int n) 75 { 76 int anc=findancestor(u,v); 77 //SET(inblossom,0); 78 memset(inblossom,0,sizeof(inblossom)); 79 reset(u,anc); 80 reset(v,anc); 81 if(base[u]!=anc)pre[u]=v; 82 if(base[v]!=anc)pre[v]=u; 83 for(int i=1; i<=n; i++) 84 if(inblossom[base[i]]) 85 { 86 base[i]=anc; 87 if(!inque[i]) 88 { 89 Q.push_back(i); 90 inque[i]=1; 91 } 92 } 93 } 94 95 bool dfs(int S,int n) 96 { 97 for(int i=0; i<=n; i++)pre[i]=-1,inque[i]=0,base[i]=i; 98 Q.clear(); 99 Q.push_back(S); 100 inque[S]=1; 101 while(!Q.empty()) 102 { 103 int u=Q.front(); 104 Q.pop_front(); 105 for(int v=1; v<=n; v++) 106 { 107 if(g[u][v]&&base[v]!=base[u]&&match[u]!=v) 108 { 109 if(v==S||(match[v]!=-1&&pre[match[v]]!=-1))contract(u,v,n); 110 else if(pre[v]==-1) 111 { 112 pre[v]=u; 113 if(match[v]!=-1)Q.push_back(match[v]),inque[match[v]]=1; 114 else 115 { 116 u=v; 117 while(u!=-1) 118 { 119 v=pre[u]; 120 int w=match[v]; 121 match[u]=v; 122 match[v]=u; 123 u=w; 124 } 125 return true; 126 } 127 } 128 } 129 } 130 } 131 return false; 132 } 133 134 void init(int n) 135 { 136 this->n = n; 137 memset(match,-1,sizeof(match)); 138 memset(g,0,sizeof(g)); 139 } 140 141 void addEdge(int a, int b) 142 { 143 ++a; 144 ++b; 145 g[a][b] = g[b][a] = 1; 146 } 147 148 int gao() 149 { 150 int ans = 0; 151 for (int i = 1; i <= n; ++i) 152 if (match[i] == -1 && dfs(i, n)) 153 ++ans; 154 return ans; 155 } 156 } match; 157 158 struct Edge 159 { 160 int u,v; 161 } edge[maxn]; 162 int deg[maxn]; 163 int D[maxn]; 164 int n,m; 165 vector<int> p[maxn]; 166 void init() 167 { 168 for(int i=0; i<maxn; i++) p[i].clear(); 169 memset(deg,0,sizeof(deg)); 170 memset(D,0,sizeof(D)); 171 } 172 void input() 173 { 174 scanf("%d%d",&n,&m); 175 for(int i=0; i<m; i++) 176 { 177 scanf("%d%d",&edge[i].u,&edge[i].v); 178 deg[--edge[i].u]++; 179 deg[--edge[i].v]++; 180 } 181 for(int i=0; i<n; i++) scanf("%d",&D[i]); 182 } 183 int solve() 184 { 185 for(int i=0; i<n; i++) if(deg[i]<D[i]) return 0; 186 int flag=1; 187 for(int i=0; i<n; i++) if(deg[i]!=D[i]) flag=0; 188 if(flag) return 1; 189 190 int cnt=0; 191 for(int k=0; k<m; k++) 192 { 193 int u=edge[k].u; 194 int v=edge[k].v; 195 if(p[u].empty()) 196 { 197 int tmp=deg[u]; 198 while(tmp>D[u]) p[u].push_back(cnt++),tmp--; 199 } 200 if(p[v].empty()) 201 { 202 int tmp=deg[v]; 203 while(tmp>D[v]) p[v].push_back(cnt++),tmp--; 204 } 205 } 206 match.init(cnt+2*m); 207 for(int k=0; k<m; k++) 208 { 209 int u=edge[k].u; 210 int v=edge[k].v; 211 match.addEdge(cnt+2*k,cnt+2*k+1); 212 for(int i=0; i<p[u].size(); i++) 213 match.addEdge(p[u][i],cnt+2*k); 214 for(int i=0; i<p[v].size(); i++) 215 match.addEdge(p[v][i],cnt+2*k+1); 216 } 217 match.gao(); 218 for(int i=1; i<=match.n; i++) if(match.match[i]==-1) return 0; 219 return 1; 220 } 221 int main() 222 { 223 // std::ios_base::sync_with_stdio(false); 224 // freopen("in.cpp","r",stdin); 225 int T; 226 scanf("%d",&T); 227 for(int kase=1; kase<=T; kase++) 228 { 229 init(); 230 input(); 231 if(solve()) printf("Case %d: YES ",kase); 232 else printf("Case %d: NO ",kase); 233 } 234 return 0; 235 }