4019022_ac_157ms_232k.cpp

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

#include <stdio.h>
#include <vector>
#include <string.h>
#include <string>
#include <algorithm>
#define inf 0xffff

using namespace std;

struct node
{
	int v;
}data[1716];

int tot;

int numOfOne(int num)
{
	int ret (0);

	while (num)
	{
		num &= (num - 1);
		ret++;
	}
	return ret;
}

void init()
{
	int i;

	tot = 0;
	for (i = 63; i <= 8064; i++)
	{
		if (numOfOne(i) == 6)
		{
			data[tot++].v = i;
		}
	}
}

int Map[20][20], link[20];
int vx[20], vy[20];
int l;

int dfs(int v)
{
	int i, t;

	for(i = 0; i < l; i++)
	{
		if(Map[v][i]&&!vy[i])
		{
			vy[i] = 1;
			t = link[i];
			link[i] = v;
			if(t==-1||dfs(t))
				return 1;
			link[i] = t;
			vx[t] = 1;
		}
	}
	return 0;
}

void KM(int edge[][20])
{
	int i, j, live, min, t;
	int lx[20], ly[20];
	int perfect;

	for(i = 0; i < l; i++)
	{
		lx[i] = 0;
		ly[i] = inf;
		for(j = 0; j < l; j++)
			if(edge[j][i]<ly[i])
				ly[i] = edge[j][i];
	}
	
	perfect = 0;
	while(!perfect)
	{
		for(i = 0; i < l; i++)
		{
			for(j = 0; j < l; j++)
			{
				if(lx[i]+ly[j]==edge[i][j])
					Map[i][j] = 1;
				else
					Map[i][j] = 0;
			}
		}
		live = 0;
		memset(link,-1,sizeof(link));
		for(i = 0; i < l; i++)
		{
			memset(vx,0,sizeof(vx));
			memset(vy,0,sizeof(vy));
			if(dfs(i))
				live++;
			else
			{
				vx[i] = 1;
				break;
			}
		}
		if(live==l)
			perfect = 1;
		else
		{
			min = inf;
			for(i = 0; i < l; i++)
				for(j = 0; vx[i]&&j < l; j++)
					if(!vy[j])
						if((t = -(lx[i]+ly[j]-edge[i][j]))<min)
							min = t;
			for(i = 0; i < l; i++)
			{
				if(vx[i])
					lx[i] += min;
				if(vy[i])
					ly[i] -= min;
			}
		}
	}
}

int dice[13][5];
int ans;
int map1[20][20], map2[20][20];
int map[13][13];

string toString(int array[])
{
	string ret = "";

	for (int i = 0; i < 5; i++)
	{
		ret += array[i] + '0';
	}
	return ret;
}

void calc()
{
	int i, j, k, score;

	for (i = 0; i < 13; i++)
	{
		sort(dice[i], dice[i] + 5);
		for (k = 1; k < 7; k++)
		{
			score = 0;
			for (j = 0; j < 5; j++)
			{
				score += k * (dice[i][j] == k);
			}
			map[i][k - 1] = score;
		}
		score = 0;
		for (j = 0; j < 5; j++)
		{
			score += dice[i][j];
		}
		map[i][6] = score;
		if (dice[i][0] == dice[i][2] || dice[i][1] == dice[i][3] || dice[i][2] == dice[i][4])
			map[i][7] = score;
		else
			map[i][7] = 0;
		if (dice[i][0] == dice[i][3] || dice[i][1] == dice[i][4])
			map[i][8] = score;
		else
			map[i][8] = 0;
		if (dice[i][0] == dice[i][4])
			map[i][9] = 50;
		else
			map[i][9] = 0;
		string tmp = toString(dice[i]);
		if (tmp.find("1234") != -1 || tmp.find("2345") != -1 || tmp.find("3456") != -1)
			map[i][10] = 25;
		else
			map[i][10] = 0;
		if (tmp == "12345" || tmp == "23456")
			map[i][11] = 35;
		else
			map[i][11] = 0;
		if ((dice[i][0] == dice[i][1] && dice[i][2] == dice[i][4]) || (dice[i][0] == dice[i][2] && dice[i][3] == dice[i][4]))
			map[i][12] = 40;
		else
			map[i][12] = 0;
	}
}

int main()
{
	int i, j, k;
	int score;
	int res[13], bouns;

	init();
	while (true)
	{
		for (i = 0; i < 13; i++)
		{
			for (j = 0; j < 5; j++)
			{
				if (scanf("%d", &dice[i][j]) == -1)
				{
					return 0;
				}
			}
		}
		ans = 0;
		calc();
		for (i = 0; i < 1716; i++)
		{
			score = 0;
			int p;
			for (k = 0; k < 6; k++)
			{
				p = 0;
				for (j = 0; j < 13; j++)
				{
					if (data[i].v & (1 << j))
					{
						map1[k][p++] = -map[j][k];
					}
				}
			}
			for (k = 6; k < 13; k++)
			{
				p = 0;
				for (j = 0; j < 13; j++)
				{
					if (!(data[i].v & (1 << j)))
					{
						map2[k - 6][p++] = -map[j][k];
					}
				}
			}
			int ans1, ans2;
			ans1 = ans2 = 0;
			l = 6;
			KM(map1);
			int ta[13];
			for (k = 0; k < l; k++)
			{
				ans1 += -map1[link[k]][k];
				ta[link[k]] = -map1[link[k]][k];
			}
			l = 7;
			KM(map2);
			int tmp = 0;
			for (k = 0; k < l; k++)
			{
				ans2 += -map2[link[k]][k];
				ta[link[k] + 6] = -map2[link[k]][k];
			}
			if (ans1 >= 63)
			{
				tmp = 1;
				ans1 += 35;
			}
			ans1 += ans2;
			if (ans1 > ans)
			{
				copy(ta, ta + 13, res);
				ans = ans1;
				bouns = tmp;
			}
		}
		for (i = 0; i < 13; i++)
			printf("%d ", res[i]);
		printf("%d %d\n", bouns * 35, ans);
	}
	return 0;
}