列表

详情

NC25398. HRY and balls

描述

When HRY was young, he like playing balls. The young boy was tidy, so on each ball he wrote a number i which means the ball belongs to box i. When playing balls, he put balls into these boxes randomly, but before bedtime, he will put them back to the boxes where they belong to.

As HRY is a little child, the way he put balls back is simple. Every time he chooses a box, pick out all the balls in the box, put every ball into the box it should be. Then he chooses another box, and repeat this operation until every ball is in the right box. The time he need for each box is the number of balls in this box now, and for any other operations the time is ignored.

As an expert of playing balls, HRY found that the order of choosing boxes greatly influenced the total time to put the balls back. But HRY is still too young, so he wants you, a JBer, to calculate how much time he needs at least to put the balls back.

输入描述

The first line contains an integer T, indicating the number of test cases. 
For each test case the first line contains two integers n, m, indicating the number of balls and the number of boxes respectively.
Then follows n lines. The ith line contains two integers a_i and b_i, which means that ball i is currently in box a_i and should be put into box b_i.

The sum of n does not exceed , and no more than 5 test cases has .

输出描述

For each test case output a line of a integer, indicating the least total time needed.

示例1

输入: 

3
2 2
1 2
2 1
2 2
1 1
1 2
2 2
1 1
2 2

输出: 

3
2
0

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 1184ms, 内存消耗: 26724K, 提交时间: 2019-04-27 22:39:26 

#include<bits/stdc++.h>
#define ll long long
#define INF  1e12 
using namespace std;
const int maxn = 1e5+5;
const int N  = 1<<18+5;
int vis[20];
int cnt[N][20];
int num[20];
ll dp[N];
int n,m;
ll dfs(int S){
	if(S==(1<<m)-1){
		return 0;
	}
	if(dp[S]!=-1)return dp[S];
	ll ret = INF;
	for(int i=0;i<m;i++){
		if((S>>i)&1)continue;
		ret = min(dfs(S|(1<<i))+(vis[i]?num[i]+cnt[S][i]:0),ret);
	} 
	return dp[S]=ret;
}
int main() {
	int T;
	scanf("%d",&T);
	while(T--) {
		cin>>n>>m;
		for(int i=0;i<m;i++){
			vis[i]=0;
			num[i]=0;
		}
		for(int i=0;i<(1<<m);i++){
			dp[i]=-1;
			for(int j=0;j<m;j++){
				cnt[i][j]=0;
			}
		}
		for(int i=0; i<n; i++) {
			int u,v;
			scanf("%d%d",&u,&v);
			u--;v--;
			num[u]++;
			cnt[1<<u][v]++;
			if(u!=v)vis[u]=1;
		}
		for(int i=1;i<(1<<m);i++){
			for(int j=0;j<m;j++){
				if((i>>j)&1){
					for(int k=0;k<m;k++){
						cnt[i][k]=cnt[1<<j][k]+cnt[i^(1<<j)][k];
					}
					break;
				}
			}
		}
		cout<<dfs(0)<<endl;
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 1348ms, 内存消耗: 25440K, 提交时间: 2019-05-12 00:24:12 

#include<bits/stdc++.h>
using namespace std;
const int maxx=20;
int a[maxx][maxx],c[maxx],f[1<<maxx][maxx];
int dp[1<<maxx];
int main() {
	int t;
	cin>>t;
	while(t--) {
		int n,m;
		cin>>n>>m;
		memset(a,0,sizeof a);
		memset(dp,0x3f,sizeof (int)*(1<<m));
		memset(f,0,sizeof (int)*(1<<m)*(20));
		memset(c,0,sizeof c);
		int need=0;
		for(int i=1; i<=n; i++) {
			int x,y;
			scanf("%d%d",&x,&y);
			x--,y--;
			a[x][y]++;
			if(x!=y) need|=1<<x;
			c[x]++;
		}

		dp[0]=0;
		for(int i=0; i<1<<m; i++) {
			for(int j=0; j<m; j++) {
				if((i&(1<<j))) {
					for(int k=0; k<m; k++) {
						f[i][k]+=a[j][k];
					}
				}
			}
		}
		for(int i=0; i<(1<<m); i++) {
			for(int j=0; j<m; j++) {
				if((i&(1<<j))) continue;
				dp[i|1<<j]=min(dp[i|1<<j],dp[i]+c[j]+f[i][j]);
			}
		}
		printf("%d\n",dp[need]);
	}
}

上一题

© 2025 nowcoder.com