本文主要是介绍poj2400--Supervisor, Supervisee(KM算法)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
po2400：题目链接
题目大意：n个老板，n个职工，每个老板有对职工的一个排名，每个职工有对老板的一个排名，排名靠前，表示满意度高，表示想去那个老板那工作或是想要某个职工，现在每个老板选择一个职工，要求最小的平均差。如果有多个的话，按字典序输出
最有的平均差 = ∑所有人距离最想要的人的差/(2*n)。
题目的描述写反了，先输入的是职工对老板的排名，然后是老板的。
对每个关系进行编号，排名第一的值为0，第二的为-1，，，老板i对于职工j的值，应该是两个人对对方的值的和，先用km算法找出最大值，也就是最优的关系，然后dfs遍历所有情况，找出最可能会出现的匹配，用已经求出的结构优化搜索
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
int Map[20][20] , n ;
int link[20] , vis[20] , cnt ;
int lx[20] , ly[20] ;
int s[20] , t[20] , ans ;
int dfs(int u) {s[u] = 1 ;for(int i = 1 ; i <= n ; i++) {if( !t[i] && lx[u]+ly[i] == Map[u][i] ) {t[i] = 1 ;if( link[i] == -1 || dfs(link[i]) ){link[i] = u ;return 1 ;}}}return 0 ;
}
void out(int dept,int temp) {if( temp > ans ) return ;if( dept > n ) {if( temp != ans ) return ;printf("Best Pairing %d\n", ++cnt) ;for(int i = 1 ; i <= n ; i++)printf("Supervisor %d with Employee %d\n", i, link[i]) ;return ;}else{for(int i = 1 ; i <= n ; i++) {if( vis[i] ) continue ;vis[i] = 1 ;link[dept] = i ;out(dept+1,temp-Map[dept][i]) ;vis[i] = 0 ;}}
}
int main() {int N , step = 0 , i , j , x , min1 , k ;scanf("%d", &N) ;while( N-- ) {memset(Map,0,sizeof(Map)) ;scanf("%d", &n) ;for(i = 1 ; i <= n ; i++)for(j = n ; j >= 1 ; j--)scanf("%d", &x) , Map[x][i] += j-n ;for(i = 1 ; i <= n ; i++)for(j = n ; j >= 1 ; j--)scanf("%d", &x) , Map[i][x] += j-n ;for(i = 1 ; i <= n ; i++){lx[i] = -100 ; ly[i] = 0 ;for(j = 1 ; j <= n ; j++)lx[i] = max(lx[i],Map[i][j]) ;}memset(link,-1,sizeof(link)) ;for(k = 1 ; k <= n ; k++) {while( 1 ) {memset(s,0,sizeof(s)) ;memset(t,0,sizeof(t)) ;if( dfs(k) ) break ;min1 = 100 ;for(i = 1 ; i <= n ; i++) {if( !s[i] ) continue ;for(j = 1 ; j <= n ; j++) {if( t[j] ) continue ;min1 = min(min1,lx[i]+ly[j]-Map[i][j]) ;}}for(i = 1 ; i <= n ; i++) {if( s[i] ) lx[i] -= min1 ;if( t[i] ) ly[i] += min1 ;}}}for(i = 1 , ans = 0 ; i <= n ; i++)if( link[i] > 0 )ans -= Map[link[i]][i] ;printf("Data Set %d, Best average difference: %.6f\n", ++step, 0.5*ans/n) ;cnt = 0 ;memset(vis,0,sizeof(vis)) ;out(1,0) ;printf("\n") ;}return 0 ;
}这篇关于poj2400--Supervisor, Supervisee(KM算法)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
