首页 > ACM题库 > HDU-杭电 > HDU 3523-Image copy detection -二分图-[解题报告]HOJ
2014
11-05

HDU 3523-Image copy detection -二分图-[解题报告]HOJ

Image copy detection

问题描述 :

The success of the Internet and cost-effective digital storage device has made it possible to replicate, transmit, and distribute digital content in an effortless way. Thus, the protection of intellectual Property right (IPR) has become a crucial legal issue. Detecting copies of digital media(images, audio and video) is a basic requirement for IPR protection (or copyright protection).The applications of copydetection include usage tracking and copyright violation enforcement.
For those above purposes, the image copy detection system came out.It aggregated all the images which were viewed as a copy of original image.In this system,an image is partitioned into m×n equalsized blocks,which makes the system independent of input image sizes,and an m×n sub-image is calculated by taking the average value of each block(see Figure.1(b)), This array is converted to a rank matrix as shown in Fig.1(c).Suppose that the intensity values in Fig.1(b) are changed in the copied image so that its sub-image has values:{{30, 60, 40}, {70, 90, 110}, {50, 100, 80}}. Nevertheless,its rank matrix is identical to that shown in Fig. 1(c) and thus perfect matching with original image can be achieved.

Minimum Integer sequence

Fig.1 (a)An image is divided into m×n blocks (3×3 in this example),(b)average values of blocks, and(c)rank matrix of (b). Let T and Q represent test image and original image,N represent the matrix size;there exists N tuples (t1,q1),…,( tn,qn),…,( tN,qN)(the order of the rank matrix:from left to right and from top to bottom).Now we define D(T,Q) = Minimum Integer sequence measures the distance between the two images(it’s obvious that if D(T,Q) gets smaller while the probability of the test image is considered as a copy of original image by the system becomes larger). Since there are M original images in the image copy detection system(Q1…QM). And the distance between T and some original images is given by D(T,Q1…QM)= Minimum Integer sequence To make it simple,we want to find an image which owns least D(T,Q1…QM).

输入:

The first line of input should give the number of cases, T (at most 100). T test cases follow. The first line of each test case contains two integer n (1 ≤ n ≤ 100) and m(1 ≤ m ≤ 100) indicating the size of rank matrix and number of original images. The following m lines each contains a sequence of n different integers denotes the rank matrix.

输出:

The first line of input should give the number of cases, T (at most 100). T test cases follow. The first line of each test case contains two integer n (1 ≤ n ≤ 100) and m(1 ≤ m ≤ 100) indicating the size of rank matrix and number of original images. The following m lines each contains a sequence of n different integers denotes the rank matrix.

样例输入:

2
3 2
1 2 3
1 3 2
9 3
1 4 2 5 7 9 3 8 6
2 1 4 5 9 3 7 6 8
9 8 7 6 5 4 3 2 1

样例输出:

Case #1: 2
Case #2: 58

HDU 3523 Image copy detection

题目链接

题意:这题其实题意读懂就简单了,说白了就是1-n放到1-n列,每列的值为每列上数字和该数字的差的绝对值,然后求总和最小

思路:就一KM最大匹配

代码:

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int MAXNODE = 505;

typedef int Type;
const Type INF = 0x3f3f3f3f;

struct KM {
	int n, m;
	Type g[MAXNODE][MAXNODE];
	Type Lx[MAXNODE], Ly[MAXNODE], slack[MAXNODE];
	int left[MAXNODE], right[MAXNODE];
	bool S[MAXNODE], T[MAXNODE];

	void init(int n, int m) {
		this->n = n;
		this->m = m;
		memset(g, 0, sizeof(g));
	}

	void add_Edge(int u, int v, Type val) {
		g[u][v] += val;
	}

	bool dfs(int i) {
		S[i] = true;
		for (int j = 0; j < m; j++) {
			if (T[j]) continue;
			Type tmp = Lx[i] + Ly[j] - g[i][j];
			if (!tmp) {
				T[j] = true;
				if (left[j] == -1 || dfs(left[j])) {
					left[j] = i;
					right[i] = j;
					return true;
				}
			} else slack[j] = min(slack[j], tmp);
		}
		return false;
	}

	void update() {
		Type a = INF;
		for (int i = 0; i < m; i++)
			if (!T[i]) a = min(a, slack[i]);
		for (int i = 0; i < n; i++)
			if (S[i]) Lx[i] -= a;
		for (int i = 0; i < m; i++)
			if (T[i]) Ly[i] += a;
	}

	Type km() {
		memset(left, -1, sizeof(left));
		memset(right, -1, sizeof(right));
		memset(Ly, 0, sizeof(Ly));
		for (int i = 0; i < n; i++) {
			Lx[i] = -INF;
			for (int j = 0; j < m; j++)
				Lx[i] = max(Lx[i], g[i][j]);
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) slack[j] = INF;
			while (1) {
				memset(S, false, sizeof(S));
				memset(T, false, sizeof(T));
				if (dfs(i)) break;
				else update();
			}
		}
		Type ans = 0;
		for (int i = 0; i < n; i++) {
			//if (right[i] == -1) return -1;
			//if (g[i][right[i]] == -INF) return -1;
			ans += g[i][right[i]];
		}
		return -ans;
	}
} gao;

int t, n, m;

int main() {
	int cas = 0;
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &n, &m);
		gao.init(n, n);
		int tmp;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				scanf("%d", &tmp);
				for (int k = 0; k < n; k++)
					gao.add_Edge(k, j, -abs(tmp - k - 1));
			}
		}
		printf("Case #%d: %d\n", ++cas, gao.km());
	}
	return 0;
}

参考:http://blog.csdn.net/accelerator_/article/details/40690461


  1. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  2. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。

  3. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }