題目鏈接：點擊查看

題目大意：給出n個老板和n個員工，現在需要進行完備匹配，具體規則是，首先給出一個n*n的矩陣，maze[i][j]=s，代表第i個員工對老板s的分數為j-1，同理接下來給出的n*n矩陣，maze[i][j]=s，代表第i個老板對員工s的分數為j-1，接下來進行完備匹配，首先規定匹配分數，若老板x和員工y匹配，則匹配分數為maze[x][y]+maze[y][x]，而平均分數是總的匹配分數除以(2*n)，現在要求在平均分數盡可能低的情況下的方案，如果有多組方案，按照字典序依次輸出

題目分析：這個題有點坑，一方面是輸入輸出的矩陣是反著的，再一方面就是O(n!)剪枝之后竟然真沒超時，可能是數據太水了吧。。首先因為是二分圖的完備匹配，而且n比較小，而且后續還需要用到鄰接矩陣進行dfs，所以用KM是最合適的選擇，主要是懶得改費用流的模板了。。先用KM反向存權值跑出來最小權匹配后，計算出平均分數，然后直接全排列找答案就好了，因為是全排列所以一定能保證字典序是最小的，記得剪枝，就是當當前匹配的權值比剛才計算的權值大時記得及時退出

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=20;int n,limit,tot;int la[N],lb[N];//頂標bool visa[N],visb[N];//訪問標記int maze[N][N];//邊權int match[N];//右部點匹配了哪一個左部點int upd[N];bool dfs(int x) {visa[x]=true;//訪問標記：x在交錯樹中for(int i=1;i<=n;i++){if(!visb[i]){if(la[x]+lb[i]-maze[x][i]==0)//相等子圖{visb[i]=true;//訪問標記：y在交錯樹中if(!match[i]||dfs(match[i])){match[i]=x;return true;}}elseupd[i]=min(upd[i],la[x]+lb[i]-maze[x][i]);}}return false; } int KM() {memset(match,0,sizeof(match));for(int i=1;i<=n;i++){la[i]=-inf;lb[i]=0;for(int j=1;j<=n;j++)la[i]=max(la[i],maze[i][j]);}for(int i=1;i<=n;i++){while(1)//直到左部點找到匹配{memset(visa,false,sizeof(visa));memset(visb,false,sizeof(visb));memset(upd,inf,sizeof(upd));if(dfs(i))break;int delta=inf;for(int j=1;j<=n;j++)if(!visb[j])delta=min(delta,upd[j]);for(int j=1;j<=n;j++)//修改頂標{if(visa[j])la[j]-=delta;if(visb[j])lb[j]+=delta;}}}int ans=0;for(int i=1;i<=n;i++)ans+=maze[match[i]][i];return ans; }bool vis[N];int ans[N];void DFS(int step,int sum)//maze[i][j]:maze[主管][員工] {if(sum<limit)return;if(step==n+1){if(sum==limit){printf("Best Pairing %d\n",++tot);for(int i=1;i<=n;i++)printf("Supervisor %d with Employee %d\n",i,ans[i]);}return;}for(int i=1;i<=n;i++){if(vis[i])continue;vis[i]=true;ans[step]=i;DFS(step+1,sum+maze[step][i]);vis[i]=false;} }void init() {memset(maze,0,sizeof(maze));memset(vis,false,sizeof(vis));tot=0; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int w;cin>>w;int kase=0;while(w--){init(); scanf("%d",&n);for(int i=1;i<=n;i++)//員工對老板 for(int j=0;j<n;j++){int num;scanf("%d",&num);maze[num][i]-=j;}for(int i=1;i<=n;i++)//老板對員工 for(int j=0;j<n;j++){int num;scanf("%d",&num);maze[i][num]-=j;}limit=KM();if(kase)printf("\n");printf("Data Set %d, Best average difference: %.6f\n",++kase,-limit*0.5/n);DFS(1,0);}return 0; }

?

總結

以上是生活随笔為你收集整理的POJ - 2400 Supervisor, Supervisee(KM+打印方案)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。