2014
11-05

# Hard Problem

This is the most tough task in this contest, do not try it until you solve all the other tasks or you feel boring on others. Given an undirected graph, you are to find out a subgraph of it so that the degree of the i-th node in the subgraph is the given integer Di. The subgraph is a subset of edges and all vertexes are reserved. Notice that the graph may be disconnected, and two edges may connect the same vertexes, but no self cyclic exists.

The input contains several test cases, the first line of the input contains an integer T denoting the number of test cases.
For each test case, the first line contains two integers N and M, denoting the number of vertexes and number of edges in the graph. (1 <= N <= 50, 1 <= M <= 200)
For the next M lines, each line contains two integers X and Y, denote there is a edge between X-th node and Y-th node. (1 <= X, Y <= N)
For the last N lines, each line contains a single integer Di, denote the degree of i-th node in the subgraph.

The input contains several test cases, the first line of the input contains an integer T denoting the number of test cases.
For each test case, the first line contains two integers N and M, denoting the number of vertexes and number of edges in the graph. (1 <= N <= 50, 1 <= M <= 200)
For the next M lines, each line contains two integers X and Y, denote there is a edge between X-th node and Y-th node. (1 <= X, Y <= N)
For the last N lines, each line contains a single integer Di, denote the degree of i-th node in the subgraph.

2
4 4
1 2
3 4
2 3
1 4
1
2
1
0
4 5
2 1
1 2
2 3
3 4
3 4
1
0
1
0

Case 1: YES
Case 2: NO

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 800;
bool mark[MAXN],in_blossom[MAXN],in_queue[MAXN];
inline void Contract (int x,int y){
memset(mark,0,sizeof(mark));
memset(in_blossom,0,sizeof(in_blossom));
#define pre fa[match[i]]
int lca,i;
for(i = x;i;i = pre){
i = base[i];
mark[i] = 1;
}
for(i = y;i; i = pre){
i = base[i];
if(mark[i]){
lca = i;
break;
}
}
for (i = x; base[i] != lca; i = pre){
if(base[pre] != lca) fa[pre] = match[i];
in_blossom[base[i]] = 1;
in_blossom[base[match[i]]] = 1;
}
for (i = y; base[i] != lca; i = pre){
if (base[pre] != lca) fa[pre] = match[i];
in_blossom[base[i]] = 1;
in_blossom[base[match[i]]] = 1;
}
#undef pre
if (base[x] != lca) fa[x] = y;
if (base[y] != lca) fa[y] = x;
for (i = 1; i <= n; ++i){
if (in_blossom[base[i]]){
base[i] = lca;
if (!in_queue[i]){
Q[++tail] = i;
in_queue[i] = 1;
}
}
}
}
inline void Change(){
int x,y,z;
z = finish;
while (z){
y = fa[z];
x = match[y];
match[y] = z;
match[z] = y;
z = x;
}
}
inline void FindAugmentPath(){
memset(fa,0,sizeof(fa));
memset(in_queue,0,sizeof(in_queue));
for(int i = 1; i <= n; ++i)base[i] = i;
head = 0; tail = 1;
Q[1] = start;
in_queue[start] = 1;
for (int y = 1; y <= n; ++y){
if (adj[x][y] && base[x] != base[y] && match[x] != y)
if (start == y || match[y] && fa[match[y]])
Contract(x,y);
else if(!fa[y]){
fa[y] = x;
if(match[y]){
Q[++tail] = match[y];
in_queue[match[y]] = 1;
}
else {
finish = y;
Change();
return;
}
}
}
}
}
inline void Edmonds(){
memset(match,0,sizeof(match));
for (start = 1; start <= n; ++start)
if (match[start] == 0)
FindAugmentPath();
}
inline void init(){
}
int deg[MAXN], D[MAXN], M;
pair<int ,int> edge[MAXN], id[MAXN];
int main(){
int Case, u, v,V;
scanf("%d",&Case);
for(int it = 1;it <= Case; ++it){
scanf("%d%d",&V,&M);
memset(deg, 0, sizeof(deg));
for(int i = 0;i < M; ++i){
scanf("%d%d",&u,&v);
u --; v --;
edge[i] = make_pair(u, v);
deg[u] ++; deg[v] ++;
}
for(int i = 0;i < V; ++i){
scanf("%d",&D[i]);
}
bool flag = true;
int cnt = 1;
for(int i = 0;i < MAXN; ++i) id[i] = make_pair(-1, -1);
for(int i = 0;i < V; ++i)
if(deg[i] < D[i]) { flag = false; break; }
printf("Case %d: ",it);
if(!flag) {
puts("NO");
continue;
}
for(int i = 0;i < M; ++i){
u = edge[i].first;
v = edge[i].second;
if(id[u].first == -1){
id[u] = make_pair(cnt, cnt + deg[u] - D[u] - 1);
cnt += (deg[u] - D[u]);
}
if(id[v].first == -1){
id[v] = make_pair(cnt, cnt + deg[v] - D[v] - 1);
cnt += (deg[v] - D[v]);
}
if(id[V+i].first == -1){
id[V+i] = make_pair(cnt, cnt + 1);
cnt += 2;
}
int t = id[V+i].first;
for(int j = id[u].first;j <= id[u].second; ++j)
for(int j = id[v].first;j <= id[v].second; ++j)
}
int j, sum = 0;
n = cnt-1;
flag = 1;
Edmonds();
for(int i = 1; i <= n; ++i){
if(!match[i]){
flag = 0;
break;
}
}
if(flag) puts("YES");
else puts("NO");
}
}

1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术，也不懂什么是算法，从而也不要求程序员懂什么算法，做程序从来不考虑性能问题，只要页面能显示出来就是好程序，这是国内的现状，很无奈。

2. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge