238
uva 11218 - KTV 簡單回溯
感覺有比回溯更加高效的方法，但是水平不夠，隻會回溯
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define INF 1E9
using namespace std;
bool h[10]={0};
int Max;
struct node
{
int a,b,c,s;
}org[82];
void dfs(int r,int i,int now)
{
if(!r)
{
Max=max(Max,now);
return;
}
for(--i;i>=0;i--)
{
if(h[org[i].a]||h[org[i].b]||h[org[i].c])continue;
h[org[i].a]=h[org[i].b]=h[org[i].c]=1;
dfs(r-1,i,now+org[i].s);
h[org[i].a]=h[org[i].b]=h[org[i].c]=0;
}
return;
}
int main()
{
int n,i,C=0;
while(~scanf("%d",&n)&&n)
{
Max=-1;
for(i=0;i<n;i++)
scanf("%d%d%d%d",&org[i].a,&org[i].b,&org[i].c,&org[i].s);
dfs(3,n,0);
printf("Case %d: %d\n",++C,Max);
}
}
最後更新：2017-04-04 07:03:44