AOJ 2558: Medical Inspection

wataさんがスライドで公開されている方法を使う。
といって使ってみたらTLEするし探索はやっぱり無理だった。(次数1の処理をしたら通った)

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>g[3100];
vector<int>ng[3100];
int deg[3100];
int use[3100];
pair<int,int>edge[31000];
int M;
int N;
int dfs(int a,int b){
	for(int i=a;i<M;i++){
		int L=edge[i].first;
		int R=edge[i].second;
		if(use[L]!=1&&use[R]!=1){
			if(b==0)return -1;
			if(deg[L]<deg[R])swap(L,R);
			int best=-1;
			// use L
			use[L]=1;
			int nb=b-1;
			vector<int>rev;
			for(int j=0;j<g[L].size();j++){
				if(use[g[L][j]]!=1){
					rev.push_back(g[L][j]);
					deg[g[L][j]]--;
				}
			}
			if(!(deg[L]<=1&&deg[R]>1))best=max(best,dfs(i+1,nb));
			for(int j=0;j<rev.size();j++)deg[rev[j]]++;
			// not use L
			use[L]=0;
			rev.clear();
			nb=b;
			for(int j=0;j<g[L].size();j++){
				if(use[g[L][j]]!=1){
					use[g[L][j]]=1;
					nb--;
					rev.push_back(g[L][j]);
				}
			}
			for(int j=0;j<rev.size();j++){
				for(int k=0;k<g[rev[j]].size();k++){
					deg[g[rev[j]][k]]--;
				}
			}
			if(nb>=0&&!(deg[L]>1&&deg[R]<=1))best=max(best,dfs(i+1,nb));
			for(int j=0;j<rev.size();j++){
				for(int k=0;k<g[rev[j]].size();k++){
					deg[g[rev[j]][k]]++;
				}
			}
			use[L]=-1;
			for(int j=0;j<rev.size();j++)use[rev[j]]=-1;
			return best;
		}
	}
	return b;
}
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	N=a;
	//M=b;
	for(int i=0;i<b;i++){
		int p,q;scanf("%d%d",&p,&q);p--;q--;
		g[p].push_back(q);
		g[q].push_back(p);
		deg[p]++;deg[q]++;
		edge[i]=make_pair(p,q);
	}
	for(int i=0;i<a;i++)use[i]=-1;
	for(int i=0;i<a;i++)if(deg[i]<1)use[i]=0;
	int rem=c;
	while(1){
		int at=-1;
		for(int i=0;i<a;i++){
			if(deg[i]>c){
				at=i;break;
			}
		}
		if(~at){
			use[at]=1;
			rem--;
			for(int i=0;i<g[at].size();i++){
				deg[g[at][i]]--;
			}
			deg[at]=0;
		}else break;
	}
	if(rem<0){
		printf("Impossible\n");return 0;
	}
	for(int i=0;i<b;i++){
		if(use[edge[i].first]!=1&&use[edge[i].second]!=1){
			edge[M++]=edge[i];
		}
	}
	if(M>c*c){
		printf("Impossible\n");return 0;
	}
	for(int i=0;i<a;i++)for(int j=0;j<g[i].size();j++){
		if(use[i]!=1&&use[g[i][j]]!=1)ng[i].push_back(g[i][j]);
	}
	for(int i=0;i<a;i++)g[i]=ng[i];
	for(int i=0;i<a;i++)deg[i]=g[i].size();
	int res=dfs(0,rem);
	if(res==-1)printf("Impossible\n");
	else printf("%d\n",c-res);
}