【题解】2015 - ICPC - shenyang E - Efficient Tree（hdu 5513）

题意 http://acm.hdu.edu.cn/showproblem.php?pid=5513

n*m的网格，横向，纵向有带权边 ， m <= 7 , n <= 800

求最小生成树的权值和

权值定义为 τ ( T ) = ∏ u L R d e g ( u ) \tau(T)=\prod_u LRdeg(u) τ(T)=∏u​LRdeg(u)

题解

轮廓线dp，最小表示法记录连通性，状态最多493个

把生成树的边权作为第一个关键字，方案数之和作为第二关键字

注意常数，不能直接用 map<vector,int> , 其实用8进制压状态更好写。每次都要先转换到最小表示再map

#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define lowbit(x) (x&(-x))
#define MP make_pair
#define fi first
#define se second
#define ls(x) (x << 1)
#define rs(x) ((x << 1) | 1)
#define rep(i,l,r) for (register int i = l ; i <= r ; i++)
#define down(i,r,l) for (register int i = r ; i >= l ; i--)
#define fore(i,x) for (int i = head[x] ; i ; i = e[i].next)
#define SZ(v) (int)v.size()

typedef long long ll;
typedef pair <int,ll> pr;
const ll mod = 1e9 + 7;
const int maxn = 1e3 + 10;
const int maxS = 500 + 10;
const int inf = 1e9;

pair <int,int> states[maxS];
unordered_map <int,int> num;
int wr[maxn][10],wc[maxn][10];
pr f[2][maxS];
int tot;
int n,m;
int col[10];

void clear(){
	num.clear();
	for (int i = 1 ; i < maxS ; i++) f[0][i] = f[1][i] = {inf,0};
	tot = 0;
}
void decode(int a[],int st){
	down(i,m,1){
		a[i] = st & 7 , st >>= 3;
	}             
}
int encode(int vec[]){
	vec[0] = 0;
	//transfer to minimum notation
 	int id = 0;
 	rep(i,1,m) col[i] = 0;
 	int res = 0;
	rep(i,1,m){
		if ( !col[vec[i]] && vec[i] ) col[vec[i]] = ++id;
		res = (res << 3) | col[vec[i]];
	}
	int &d = num[res];
	if ( d ) return d;
	states[++tot] = {res,id};
	assert(tot < maxS);
	return d = tot;
}
bool check(int vec[],int j){
	rep(i,1,m){
		if ( vec[i] == vec[j] && i != j ) return 1;
	}
	return 0;
}
void up(pr &cur,int w,ll cnt){
	if ( cur.fi > w ){
		cur.fi = w;
		cur.se = cnt;
	}
	else if ( cur.fi == w ){
		cur.se = (cur.se + cnt) % mod;
	}
}
int main(){
	freopen("input.txt","r",stdin);
	int cases;
	scanf("%d",&cases);
	rep(t,1,cases){
	//	double times = clock();
		printf("Case #%d: ",t);
		scanf("%d %d",&n,&m);
		rep(i,1,n) rep(j,1,m - 1) scanf("%d",&wr[i][j]);
		rep(i,1,n - 1) rep(j,1,m) scanf("%d",&wc[i][j]);

		clear();
		int now = 1 , last = 0;
		//vector <int> empty(m + 1,0);
		int cur[8];
		rep(i,1,m) cur[i] = 0;
		f[now][encode(cur)] = {0,1};
		rep(i,1,n){
			rep(j,1,m){
				last = now , now ^= 1;
				rep(k,1,tot) f[now][k] = {inf,0};
				rep(k,1,tot){
					if ( !f[last][k].se ) continue;
					int w = f[last][k].fi; ll cnt = f[last][k].se;
					//cout<<i<<" "<<j<<" "<<k<<" "<<w<<" "<<cnt<<endl;
					int st = states[k].fi; int cnt_c = states[k].se;
					decode(cur,st);
					if ( i == 1 ){ //no edges up
						if ( j == 1 ){
							cur[j] = 1;
							up(f[now][encode(cur)],w,cnt);
						}
						else{
							cur[j] = cur[j - 1];
							up(f[now][encode(cur)],w + wr[i][j - 1],cnt * 2 % mod);
							cur[j] = cnt_c + 1;
							up(f[now][encode(cur)],w,cnt);
						}
					}
					else{
						int tmp;
						//no edge
						if ( check(cur,j) ){
							tmp = cur[j];
							cur[j] = cnt_c + 1;
							up(f[now][encode(cur)],w,cnt);
							cur[j] = tmp;

							//only left
							if ( j > 1 ){
								tmp = cur[j];
								cur[j] = cur[j - 1];
								up(f[now][encode(cur)],w + wr[i][j - 1],cnt * 2 % mod);
								cur[j] = tmp;
							}
						}
						//only up
						up(f[now][num[st]],w + wc[i - 1][j],cnt * 2 % mod);
						
						// both up and left
						if ( j > 1 && cur[j - 1] != cur[j] ){
							int tmp = cur[j];
							rep(l,1,m) if ( cur[l] == tmp ) cur[l] = cur[j - 1];
							up(f[now][encode(cur)],w + wr[i][j - 1] + wc[i - 1][j],cnt * 3 % mod);
						}
					}
				}
			}
		}
		rep(i,1,m) cur[i] = 1;
		int st = encode(cur);
		//cout<<st<<endl;
		printf("%d %lld\n",f[now][st].fi,f[now][st].se);
	//	cout<<(clock() - times) / CLOCKS_PER_SEC<<" "<<tot<<endl;
	}
	
}