hdu 3718 Similarity (二分图最优匹配，KM算法)

2016-06-02 · 2 min read · KM 二分图最佳匹配

hdu 3718题目链接

题意：东西分类作业，有n个东西,k组，m个学生，不同种类的东西用不同的字母表示，相同种类的用同一个字母表示。不同学生和标准答案之间可能表示同一类东西用的字母不同，但是字母只是一个标号（But the LABEL of group doesn't make sense and the LABEL is just used to indicate different groups. ） 给出事物分类的标准答案和每个学生的答案现在问每个学生的正确率是多少。

思路：用map<char,int>把字母转化成点的标号。然后初始化权值为0. 对于每个学生，o(n)扫一遍统计出w。然后做一遍KM求最大正确数。从而得到正确率。 因为一个map忘记每次清空，WA了一次。。。2A..

/* ***********************************************
Author :111qqz
Created Time :2016年06月03日 星期五 01时32分27秒
File Name :code/hdu/3718.cpp
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair

 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6const int N=1E4+7;
 7int n,k,m;
 8char a[35][N];
 9int w[35][35];
10map<char,int>mp1,mp2;
11int tot1,tot2;
12int lx[35],ly[35];
13bool visx[35],visy[35];
14int link[35];
15int slk[35];

 1bool find( int u)
 2{
 3    visx[u] = true;
 4    for ( int v = 1 ; v <= k ; v++)
 5    {
 6	if (visy[v]) continue;
 7	int tmp = lx[u] + ly[v] - w[u][v];
 8	if (tmp==0)
 9	{
10	    visy[v] = true;
11	    if (link[v]==-1||find(link[v]))
12	    {
13		link[v] = u;
14		return true;
15	    }
16	}else if (tmp<slk[v]) slk[v] = tmp;
17    }
18    return false;
19}
20int KM()
21{
22    ms(link,-1);
23    ms(lx,0);
24    ms(ly,0);

1    for ( int i = 1 ; i <= tot2 ; i++)
2	for ( int j = 1 ; j <= k ; j++)
3	    lx[i] = max(lx[i],w[i][j]);

1    for ( int i = 1 ; i <= tot2 ; i++)
2    {
3	ms(slk,0x3f);

1	while (1)
2	{
3	    ms(visx,false);
4	    ms(visy,false);

	    if (find(i)) break;

	    int d = inf;

	    for ( int j = 1 ;j <= k ; j++) 
		if (!visy[j]&&slk[j]<d) d = slk[j];

 1	    for ( int j = 1 ; j <= tot2 ; j++)
 2		if (visx[j]) lx[j]-=d;
 3	    for ( int j = 1; j <= k ; j++)
 4		if (visy[j]) ly[j]+=d; else slk[j]-=d;
 5	}
 6    }
 7    int res = 0 ;
 8    for ( int i = 1 ;  i <= k  ; i++)
 9	if (link[i]>-1) res += w[link[i]][i];
10    return res;
11}
12int main()
13{
14	#ifndef  ONLINE_JUDGE 
15	freopen("code/in.txt","r",stdin);
16  #endif

 1	int T;
 2	cin>>T;
 3	while (T--)
 4	{
 5	    ms(w,0);
 6	    mp1.clear();
 7	    mp2.clear();
 8	    tot1 = 0 ;
 9	    tot2 = 0 ;
10	    scanf("%d%d%d",&n,&k,&m);
11	    getchar();
12	    for ( int i = 0 ; i <= m ; i++)
13	    {
14		for ( int j = 1 ; j <= n ; j++)
15		    scanf(" %c",&a[i][j]);
16		getchar();

	//	for ( int j = 1 ; j <= n ; j++) cout<<a[i][j]<<" ";

	//	cout<<endl;
	    }
	    
	    for ( int i = 1 ; i <= n ; i++) if (!mp1[a[0][i]]) mp1[a[0][i]]=++tot1;

1	    for ( int i = 1;  i <= m ; i++)
2	    {
3		ms(w,0);
4		tot2 = 0 ;
5		mp2.clear();

		for ( int j = 1 ; j <= n ; j++) if (!mp2[a[i][j]]) mp2[a[i][j]] = ++tot2;

1		for ( int j =  1; j <= n ; j++) 
2		{
3		    int u = mp1[a[0][j]];
4		    int v = mp2[a[i][j]];
5		    w[v][u]++;
6		}

1		int ret = KM();
2		double ans;
3		ans = ret*1.0/(n*1.0);
4		printf("%.4f\n",ans);
5	    }

	}

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}