CHNREST - Chinese restaurant
Tác giả: hieult
Ngôn ngữ: Java
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
* @author HIEULT01060
*/
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException{
int m,n;
int a[] = new int[33];
int b[] = new int[33];
int f[] = new int[60000];
int u[][] = new int [13][33];
int x;
int mu2[] = new int[20],mu3[] = new int[20];
mu2[0] = 1; mu3[0] = 1;
for(int i = 1;i<=16;i++)
{
mu2[i] = mu2[i-1]*2;
mu3[i] = mu3[i-1]*3;
}
int max = 1000000000;
for(int i = 0;i<60000;i++)
f[i] = max;
int kq = max;
String s;
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
//RandomAccessFile fa = new RandomAccessFile ("CHNREST.in","r");
s = in.readLine();
// s = fa.readLine();
StringTokenizer st = new StringTokenizer(s," ");
m = Integer.parseInt(st.nextToken());
n = Integer.parseInt(st.nextToken());
s = in.readLine();
// s = fa.readLine();
st = new StringTokenizer(s," ");
for(int i = 1;i<=m;i++) a[i] = Integer.parseInt(st.nextToken());
for(int i = 1;i<=n;i++)
{
s = in.readLine();
//s = fa.readLine();
st = new StringTokenizer(s," ");
while(st.hasMoreTokens())
{
x = Integer.parseInt(st.nextToken());
u[i][x] = 1;
}
}
int m1 = m/2, m2 = m-m/2;
for(int i = 0;i<mu2[m1];i++)
{
int run=0,r,the = i,tien=0;
for(int j = 1;j<=n;j++)
b[j] = 0;
for(int j = 0;j<m1;j++)
{
run++;
r = the%2;
if(r==1)
{
for(int k = 1;k<=n;k++)
if(u[k][run]==1)
b[k]++;
tien+=a[run];
}
the = the/2;
}
int flag = 0,tong = 0;
for(int j = 1;j<=n;j++)
{
if(b[j]>2)
{
flag = 1;
break;
}
else tong = tong+b[j]*mu3[j-1];
}
if(flag==0)
f[tong]=Math.min(tien,f[tong]);
}
for(int i = 0;i<mu2[m2];i++)
{
int run=0,r,the = i,tien=0;
for(int j = 1;j<=n;j++)
b[j] = 0;
for(int j = 0;j<m2;j++)
{
run++;
r = the%2;
if(r==1)
{
for(int k = 1;k<=n;k++)
if(u[k][run+m1]==1)
b[k]++;
tien+=a[run+m1];
}
the = the/2;
}
int flag = 0,tong = 0;
for(int j = 1;j<=n;j++)
{
if(b[j]>2)
{
flag = 1;
break;
}
else tong = tong+mu3[j-1]*(2-b[j]);
}
if(flag == 0)
kq = Math.min(kq, f[tong]+tien);
}
if(kq>=max)
System.out.print("-1");
else System.out.print(kq);
}
}