2962938_ac_0ms_116k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string>
#include <cassert>
#include <algorithm>
#define inf 1000000
using namespace std;

int n, m;
string name[13];
struct node
{
	int num[13];
	int adj[13][13];
	int finished[13];
};
node map;
int ans;
char style[13];
const char ch[] = "SF";
int mark[13];
int over;

void solve(int s,node t);

int get_id(string t)
{
	int i;

	for(i = 0; i < n; i++)
	{
		if(t==name[i])
		{
			return i;
		}
	}
	assert(NULL);
	return -1;
}

void release(int id,node &t)
{
	int i;

	t.finished[id] = 1;
	for(i = 0; i < n; i++)
	{
		if(t.adj[i][id]==1)
		{
			t.adj[i][id] = 0;
			t.num[i]--;
		}
	}
}

int finished(node t)
{
	int i;

	for(i = 0; i < n; i++)
	{
		if(t.finished[i]==0)
		{
			return 0;
		}
	}
	return 1;
}

void enumerate(int st,int s,node t,int acc,int cnt,int sel[])
{
	int i;

	if(over)
		return ;
	if(acc==0)
	{
		for(i = 0; i < cnt; i++)
		{
			if(mark[i]==1)
			{
				release(sel[i],t);
			}	
		}
		solve(s+1,t);
		return ;
	}
	for(i = st; !over&&i <= cnt-acc; i++)
	{
		mark[i] = 1;
		enumerate(i+1,s,t,acc-1,cnt,sel);
		mark[i] = 0;
	}
}

void solve(int s,node t)
{
	int i;
	int sel[13], cnt;
	node tmp = t;

	if(ans<=n/m+(n%m!=0))
	{
		over = 1;
		return ;
	}
	if(over)
		return ;
	if(finished(t))
	{
		if(s < ans)
		{
			ans = s;
		}
		return ;
	}
	cnt = 0;
	for(i = 0; i < n; i++)
	{
		if(t.finished[i]==0&&t.num[i]==0&&style[i]!=ch[s%2])
		{
			sel[cnt++] = i;
		}
	}
	if(cnt <= m)
	{
		for(i = 0; i < cnt; i++)
		{
			release(sel[i],tmp);
		}
		solve(s+1,tmp);
	}
	else
	{
		memset(mark,0,sizeof(mark));
		enumerate(0,s,t,m,cnt,sel);
	}
}

int main()
{
	int i, j, p, id;
	char tmp[6];
	string t;

	while(scanf("%d%d",&n,&m)==2)
	{
		if(n==-1&&m==-1)
			break;
		over = 0;
		memset(map.adj,0,sizeof(map.adj));
		memset(map.finished,0,sizeof(map.finished));
		for(i = 0; i < n; i++)
		{
			scanf("%s",tmp);
			name[i] = tmp;
		}
		for(i = 0; i < n; i++)
		{
			scanf("%s",tmp);
			t = tmp;
			id = get_id(t);
			scanf("%s",tmp);
			style[id] = tmp[0];
			scanf("%d",&p);
			map.num[id] = p;
			for(j = 0; j < p; j++)
			{
				scanf("%s",tmp);
				t = tmp;
				map.adj[id][get_id(t)] = 1;
			}
		}
		ans = inf;
		solve(0,map);
		printf("The minimum number of semesters required to graduate is %d.\n",ans);
	}
	return 0;
}