Submit Info #38427

Problem Lang User Status Time Memory
Assignment Problem cpp hiiragi4000 AC 128 ms 2.61 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
hand_minus_00 AC 81 ms 2.53 MiB
hand_plus_00 AC 99 ms 2.61 MiB
max_random_00 AC 122 ms 2.55 MiB
max_random_01 AC 120 ms 2.48 MiB
max_random_02 AC 98 ms 2.48 MiB
max_random_03 AC 128 ms 2.61 MiB
max_random_04 AC 128 ms 2.55 MiB
random_00 AC 8 ms 1.30 MiB
random_01 AC 12 ms 1.42 MiB
random_02 AC 3 ms 0.99 MiB
random_03 AC 13 ms 1.42 MiB
random_04 AC 1 ms 0.73 MiB

#include<algorithm> #include<vector> #include<climits> #include<cstdio> #include<cstring> using namespace std; using i64 = long long; #define MAXN 500 #define INF (LLONG_MAX/2) int n; i64 g[MAXN][MAXN],lx[MAXN],ly[MAXN],slack_y[MAXN]; int match_y[MAXN]; bool vx[MAXN],vy[MAXN]; bool dfs(int x){ if(vx[x])return 0; vx[x]=1; for(int y=0;y<n;++y){ if(vy[y])continue; i64 t=lx[x]+ly[y]-g[x][y]; if(t==0){ vy[y]=1; if(match_y[y]==-1||dfs(match_y[y])){ match_y[y]=x; return 1; } }else if(slack_y[y]>t)slack_y[y]=t; } return 0; } inline i64 km(){ memset(ly,0,n*sizeof*ly); memset(match_y,-1,n*sizeof*match_y); for(int x=0;x<n;++x){ lx[x]=-INF; for(int y=0;y<n;++y){ lx[x]=max(lx[x],g[x][y]); } } for(int x=0;x<n;++x){ for(int y=0;y<n;++y)slack_y[y]=INF; for(;;){ memset(vx,0,sizeof(bool)*n); memset(vy,0,sizeof(bool)*n); if(dfs(x))break; i64 cut=INF; for(int y=0;y<n;++y){ if(!vy[y]&&cut>slack_y[y])cut=slack_y[y]; } for(int j=0;j<n;++j){ if(vx[j])lx[j]-=cut; if(vy[j])ly[j]+=cut; else slack_y[j]-=cut; } } } i64 ans=0; for(int y=0;y<n;++y)if(g[match_y[y]][y]!=-INF)ans+=g[match_y[y]][y]; return ans; } int main(){ scanf("%d", &n); for(int i=0; i<n; ++i) for(int j=0; j<n; ++j){ scanf("%lld", g[i]+j); g[i][j] = -g[i][j]; } printf("%lld\n", -km()); vector<int> p(n); for(int i=0; i<n; ++i){ p[match_y[i]] = i; } for(int i=0; i<n; ++i){ printf("%d%c", p[i], " \n"[i==n-1]); } }