題目：奔小康賺大錢

?

KM算法深入理解：請戳這里

?

#include <stdio.h> #include <string.h> #define INF 99999999 #define N 350int n,nx,ny; //nx,ny分別表示x集合和y集合的元素個數int lx[N]; int ly[N]; int link[N]; int slack[N]; int visx[N]; int visy[N]; int w[N][N];bool DFS(int x) {int y;visx[x]=1;for(y=1;y<=ny;y++){if(visy[y]) continue;int t=lx[x]+ly[y]-w[x][y];if(t==0){visy[y]=1;if(link[y]==-1||DFS(link[y])){link[y]=x;return true;}}else if(slack[y]>t) //不在相等子圖中slack 取最小的slack[y]=t;}return false; }int KM() {int i,j,x;memset(link,-1,sizeof(link));memset(ly,0,sizeof(ly));for(i=1;i<=nx;i++) //lx初始化為與它關聯邊中最大的for(j=1,lx[i]=-INF;j<=ny;j++)if(w[i][j]>lx[i])lx[i]=w[i][j];for(x=1;x<=nx;x++){for(i=1;i<=ny;i++)slack[i]=INF;while(1){memset(visx,0,sizeof(visx));memset(visy,0,sizeof(visy));if(DFS(x)) break; //若成功（找到了增廣軌），則該點增廣完成，進入下一個點的增廣//若失敗（沒有找到增廣軌），則需要改變一些點的標號，使得圖中可行邊的數量增加。//方法為：將所有在增廣軌中（就是在增廣過程中遍歷到）的X方點的標號全部減去一個常數d，//所有在增廣軌中的Y方點的標號全部加上一個常數dint d=INF;for(i=1;i<=ny;i++)if(!visy[i]&&d>slack[i])d=slack[i];for(i=1;i<=nx;i++)if(visx[i])lx[i]-=d;for(i=1;i<=ny;i++) //修改頂標后，要把所有不在交錯樹中的Y頂點的slack值都減去d{if(visy[i]) ly[i]+=d;else slack[i]-=d;}}}int ans=0;for(i=1;i<=ny;i++)if(link[i]>-1)ans+=w[link[i]][i];return ans; }int main() {int i,j;while(~scanf("%d",&n)){nx=ny=n;memset(w,0,sizeof(w));for(i=1;i<=n;i++)for(j=1;j<=n;j++)scanf("%d",&w[i][j]);int ans=KM();printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的HDU2255(带权二分图的最大匹配)的全部內容，希望文章能夠幫你解決所遇到的問題。

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