首页 > ACM题库 > HDU-杭电 > HDU 3551-Hard Problem[解题报告]HOJ
2014
11-05

HDU 3551-Hard Problem[解题报告]HOJ

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;
int n,head,tail,start,finish,match[MAXN],fa[MAXN],base[MAXN],Q[MAXN];//match��ʼΪ0 n�����ͼ ��1��ʼ
int adj[MAXN][MAXN]; //�ڽӾ���
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;
		while (head != tail){
				int x = Q[++head];
				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(){
	memset(adj,0,sizeof(adj));
}
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));
				memset(adj, 0, sizeof(adj));
				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;
						adj[t][t+1] = adj[t+1][t] = true;
						for(int j = id[u].first;j <= id[u].second; ++j)
								adj[t][j] = adj[j][t] = true;
						for(int j = id[v].first;j <= id[v].second; ++j)
								adj[t+1][j] = adj[j][t+1] = true;
				}
				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

  3. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。