POJ 2400 最小权匹配-白红宇

POJ 2400 最小权匹配

阅读量：4598 次

发布时间：2019-06-09

本文共 3183 字，大约阅读时间需要 10 分钟。

吐槽：首先，这道题的输入居然是错的。要将上下两个矩阵的位置换一下才可以出样例，也就是上面那个矩阵是employee对Supervisor的打分，下面那个矩阵才是Supervisor对employee的打分。

题意：给出两个矩阵，分别是employee对supervision的打分和supervision对employee的打分。当然矩阵中给出的不是分数，而是进来的先后顺序，第一个进来的分数就是1，第二个。。。类推，然后分数越低对这个部门越喜欢，同理下一个矩阵。

然后叫你求出，使得他们都最满意的方案，并且输出平均不满意度，这个平均不满意度就是，假设a这个人到b这个部分，他的分数是1，但是完备匹配后，他被分配到了c，他对c的分数是2，那么他的不满意度就是1，然后平均不满意度就是不满意度的总和/(2 * n) 。

思路：建图，对于每个employe和supervision，连一条边，权值是他们互相的分数的总和。

然后就是求一次最小权匹配，因为权值越小他们越满意。最后输出平均不满意度的时候，为什么要 - 2 * n 呢，假设所有的employee和supervision都匹配到了他们权值最小的边，那么这条边的值就是2，所以如果当前是的匹配结果的权值是2 * n 的话，那么所有人都是在他最满意的位置上，所以不满意度就是0.

CODE：

#include 
    
     #include 
     #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #define Max 2505#define FI first#define SE second#define ll long long#define PI acos(-1.0)#define inf 0x3fffffff#define LL(x) ( x << 1 )#define bug puts("here")#define PII pair
                
                 #define RR(x) ( x << 1 | 1 )#define mp(a,b) make_pair(a,b)#define mem(a,b) memset(a,b,sizeof(a))#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )using namespace std;inline void RD(int &ret) { char c; int flag = 1 ; do { c = getchar(); if(c == '-')flag = -1 ; } while(c < '0' || c > '9') ; ret = c - '0'; while((c=getchar()) >= '0' && c <= '9') ret = ret * 10 + ( c - '0' ); ret *= flag ;}#define N 22int n ;int Map[N][N] ;int lx[N] , ly[N] , visx[N] , visy[N] ,linkx[N] , linky[N] ;int find(int now){ visx[now] = 1 ; for (int i = 1 ; i <= n ; i ++ ){ if(!visy[i]){ int fk = Map[now][i] - lx[now] - ly[i] ; if(!fk){ visy[i] = 1 ; if(linky[i] == -1 || find(linky[i])){ linky[i] = now ; linkx[now] = i ; return 1 ; } } } } return 0 ;}int KM(){ mem(linky ,-1) ; mem(ly ,0) ; for (int i = 1 ; i <= n ; i ++ ){ lx[i] = inf ; for (int j = 1 ; j <= n ; j ++ )lx[i] = min(lx[i] , Map[i][j]) ; } for (int i = 1 ; i <= n ; i ++ ){ while(1){ mem(visx, 0) ;mem(visy, 0) ; if(find(i))break ; int d = inf ; for (int j = 1 ; j <= n ; j ++ ) if(visx[j]) for (int k = 1 ; k <= n ; k ++ ) if(!visy[k]) d = min(d , Map[j][k] - lx[j] - ly[k]) ; for (int j = 1 ; j <= n ; j ++ ){ if(visx[j])lx[j] += d ; if(visy[j])ly[j] -= d ; } } } int ans = 0 ; for (int i = 1 ; i <= n ; i ++ ){ if(linky[i] != -1)ans += Map[linky[i]][i] ; } return ans ;}int cnt , ans ;bool vis[N] ;int ffk[N] ;void dfs(int dp , int sum){ if(sum > ans)return ; if(dp > n){ if(sum == ans){ printf("Best Pairing %d\n",++ cnt) ; for (int i = 1 ; i <= n ; i ++ ){ printf("Supervisor %d with Employee %d\n",i , ffk[i]) ; } } return ; } else for (int i = 1 ; i <= n ; i ++ ){ if(!vis[i]){ vis[i] = 1 ; ffk[dp] = i ; dfs(dp + 1 , sum + Map[dp][i]) ; vis[i] = 0 ; } }}int main() { int t ; cin >> t ; int ca = 0 ; while(t -- ){ cin >> n ; cnt = 0 ; mem(Map ,0) ; for (int i = 1 ; i <= n ; i ++ ){ for (int j = 1 ; j <= n ; j ++ ){ int fk ; RD(fk) ; Map[fk][i] += j ; } } for (int i = 1 ; i <= n ; i ++ ){ for (int j = 1 ; j <= n ; j ++ ){ int fk ; RD(fk) ; Map[i][fk] += j ; } } mem(vis ,0) ; ans = KM() ; printf("Data Set %d, Best average difference: %f\n",++ ca ,( ans - n * 2 ) * 0.5 / n) ; dfs(1 , 0) ; puts("") ; } return 0 ;}

转载于:https://www.cnblogs.com/james1207/p/3290225.html

你可能感兴趣的文章