POJ 2400 最小权匹配
吐槽:首先,这道题的输入居然是错的。要将上下两个矩阵的位置换一下才可以出样例,也就是上面那个矩阵是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 <set> #include <map> #include <stack> #include <cmath> #include <queue> #include <cstdio> #include <string> #include <vector> #include <iomanip> #include <cstring> #include <iostream> #include <algorithm> #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<int,int> #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 22 int 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 ; }
补充:软件开发 , C++ ,