1 条题解
-
0
C++ :
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 25; const int INF = 0x7f7f7f7f; #define MIN(a,b) a<b?a:b int n,match[N]; bool sx[N],sy[N]; int lx[N],ly[N],map[N][N]; int p[25][25],q[25][25]; bool path(int u) { sx[u]=true; for(int v=0; v<n; v++) if(!sy[v]&&lx[u]+ly[v]==map[u][v]) { sy[v]=true; if(match[v]==-1||path(match[v])) { match[v]=u; return true; } } return false; } int KM(bool truth) { int i,j; if(!truth) { for(i=0; i<n; i++) for(j=0; j<n; j++) map[i][j]=-map[i][j]; } memset(lx,0,sizeof(lx)); memset(ly,0,sizeof(ly)); memset(match,-1,sizeof(match)); for(int u=0; u<n; u++) while(1) { memset(sx,0,sizeof(sx)); memset(sy,0,sizeof(sy)); if(path(u)) break; int dmin=INF; for(i=0; i<n; i++) if(sx[i]) for(j=0; j<n; j++) if(!sy[j]) dmin=MIN(lx[i]+ly[j]-map[i][j],dmin); for(i=0; i<n; i++) { if(sx[i]) lx[i]-=dmin; if(sy[i]) ly[i]+=dmin; } } int sum=0; for(j=0; j<n; j++) sum+=map[match[j]][j]; if(!truth) { sum=-sum; for(i=0; i<n; i++) for(j=0; j<n; j++) map[i][j]=-map[i][j]; } return sum; } void Map_Init(int n) { int i,j; for(i=0; i<n; i++) for(j=0; j<n; j++) map[i][j]=-p[i][j]*q[j][i]; } int main() { int i,j; scanf("%d",&n); for(i = 0; i <n; i++) for(j = 0; j <n; j++) scanf("%d",&p[i][j]); for(i = 0; i <n; i++) for(j =0 ; j <n; j++) scanf("%d",&q[i][j]); Map_Init(n); int cost=KM(false); printf("%d\n",-cost); return 0; }
- 1
信息
- ID
- 119
- 时间
- 5000ms
- 内存
- 128MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者