TIOJ 1042 老問題

TIOJ 1042 老問題

題目概述:

二分圖最大權完美匹配 裸題。

注意負數要改成0。

思路:

以下給出的做法為O(N^4)，且無特別優化。

但個人認為這是比較直觀且比較好寫不會有bug的寫法。

有的時候太注重再一些優化，反而在競賽時會出一些bug。

//By SCJ

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

#define INF 10000000

int n,a[102][102],lx[102],ly[102],match[102];

bool vx[102],vy[102];

bool dfs(int x)

{

   vx[x]=1;

   for(int y=1;y<=n;++y)

   {

       if(vy[y]) continue;

       int d=lx[x]+ly[y]-a[x][y];

       if(d==0)

       {

           vy[y]=1;

           if(match[y]==-1||dfs(match[y]))

           {

               match[y]=x;

               return 1;

           }

       }

   }

   return 0;

}

int KM()

{

   memset(match,-1,sizeof(match));

   for(int i=1;i<=n;++i)

   {

       lx[i]=-INF;

       for(int j=1;j<=n;++j)

           lx[i]=max(lx[i],a[i][j]);

   }

   for(int x=1;x<=n;++x)

   {

       while(1)

       {

           memset(vx,0,sizeof(vx));

           memset(vy,0,sizeof(vy));

           if(dfs(x)) break;

           int d=INF;

           for(int i=1;i<=n;++i) if(vx[i])

               for(int j=1;j<=n;++j) if(!vy[j])

                   d=min(d,lx[i]+ly[j]-a[i][j]);

           for(int i=1;i<=n;++i)

           {

               if(vx[i]) lx[i]-=d;

               if(vy[i]) ly[i]+=d;

           }

       }

   }

   int ans=0;

   for(int i=1;i<=n;++i) ans+=lx[i]+ly[i];

   return ans;

}

int main()

{

ios::sync_with_stdio(0);

cin.tie(0);

   while(cin>>n,n!=0)

   {

       for(int i=1;i<=n;++i)

           for(int j=1;j<=n;++j) cin>>a[i][j],a[i][j]=max(a[i][j],0);

       cout<<KM()<<endl;

   }

}