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..

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年06月03日 星期五 01时32分27秒
  4File Name :code/hdu/3718.cpp
  5************************************************ */
  6
  7#include <cstdio>
  8#include <cstring>
  9#include <iostream>
 10#include <algorithm>
 11#include <vector>
 12#include <queue>
 13#include <set>
 14#include <map>
 15#include <string>
 16#include <cmath>
 17#include <cstdlib>
 18#include <ctime>
 19#define fst first
 20#define sec second
 21#define lson l,m,rt<<1
 22#define rson m+1,r,rt<<1|1
 23#define ms(a,x) memset(a,x,sizeof(a))
 24typedef long long LL;
 25#define pi pair < int ,int >
 26#define MP make_pair
 27
 28using namespace std;
 29const double eps = 1E-8;
 30const int dx4[4]={1,0,0,-1};
 31const int dy4[4]={0,-1,1,0};
 32const int inf = 0x3f3f3f3f;
 33const int N=1E4+7;
 34int n,k,m;
 35char a[35][N];
 36int w[35][35];
 37map<char,int>mp1,mp2;
 38int tot1,tot2;
 39int lx[35],ly[35];
 40bool visx[35],visy[35];
 41int link[35];
 42int slk[35];
 43
 44
 45bool find( int u)
 46{
 47    visx[u] = true;
 48    for ( int v = 1 ; v <= k ; v++)
 49    {
 50	if (visy[v]) continue;
 51	int tmp = lx[u] + ly[v] - w[u][v];
 52	if (tmp==0)
 53	{
 54	    visy[v] = true;
 55	    if (link[v]==-1||find(link[v]))
 56	    {
 57		link[v] = u;
 58		return true;
 59	    }
 60	}else if (tmp<slk[v]) slk[v] = tmp;
 61    }
 62    return false;
 63}
 64int KM()
 65{
 66    ms(link,-1);
 67    ms(lx,0);
 68    ms(ly,0);
 69
 70    for ( int i = 1 ; i <= tot2 ; i++)
 71	for ( int j = 1 ; j <= k ; j++)
 72	    lx[i] = max(lx[i],w[i][j]);
 73
 74    for ( int i = 1 ; i <= tot2 ; i++)
 75    {
 76	ms(slk,0x3f);
 77
 78	while (1)
 79	{
 80	    ms(visx,false);
 81	    ms(visy,false);
 82
 83	    if (find(i)) break;
 84
 85	    int d = inf;
 86
 87	    for ( int j = 1 ;j <= k ; j++) 
 88		if (!visy[j]&&slk[j]<d) d = slk[j];
 89
 90	    for ( int j = 1 ; j <= tot2 ; j++)
 91		if (visx[j]) lx[j]-=d;
 92	    for ( int j = 1; j <= k ; j++)
 93		if (visy[j]) ly[j]+=d; else slk[j]-=d;
 94	}
 95    }
 96    int res = 0 ;
 97    for ( int i = 1 ;  i <= k  ; i++)
 98	if (link[i]>-1) res += w[link[i]][i];
 99    return res;
100}
101int main()
102{
103	#ifndef  ONLINE_JUDGE 
104	freopen("code/in.txt","r",stdin);
105  #endif
106
107	int T;
108	cin>>T;
109	while (T--)
110	{
111	    ms(w,0);
112	    mp1.clear();
113	    mp2.clear();
114	    tot1 = 0 ;
115	    tot2 = 0 ;
116	    scanf("%d%d%d",&n,&k,&m);
117	    getchar();
118	    for ( int i = 0 ; i <= m ; i++)
119	    {
120		for ( int j = 1 ; j <= n ; j++)
121		    scanf(" %c",&a[i][j]);
122		getchar();
123
124	//	for ( int j = 1 ; j <= n ; j++) cout<<a[i][j]<<" ";
125
126	//	cout<<endl;
127	    }
128
129	    for ( int i = 1 ; i <= n ; i++) if (!mp1[a[0][i]]) mp1[a[0][i]]=++tot1;
130
131	    for ( int i = 1;  i <= m ; i++)
132	    {
133		ms(w,0);
134		tot2 = 0 ;
135		mp2.clear();
136
137		for ( int j = 1 ; j <= n ; j++) if (!mp2[a[i][j]]) mp2[a[i][j]] = ++tot2;
138
139		for ( int j =  1; j <= n ; j++) 
140		{
141		    int u = mp1[a[0][j]];
142		    int v = mp2[a[i][j]];
143		    w[v][u]++;
144		}
145
146		int ret = KM();
147		double ans;
148		ans = ret*1.0/(n*1.0);
149		printf("%.4f\n",ans);
150	    }
151
152
153
154	}
155
156  #ifndef ONLINE_JUDGE  
157  fclose(stdin);
158  #endif
159    return 0;
160}