Submit Info #67379

Problem Lang User Status Time Memory
Assignment Problem cpp (anonymous) AC 293 ms 8.16 MiB

ケース詳細
Name Status Time Memory
example_00 AC 5 ms 8.07 MiB
hand_minus_00 AC 293 ms 8.07 MiB
hand_plus_00 AC 257 ms 8.07 MiB
max_random_00 AC 70 ms 8.10 MiB
max_random_01 AC 67 ms 8.07 MiB
max_random_02 AC 64 ms 8.07 MiB
max_random_03 AC 73 ms 8.03 MiB
max_random_04 AC 70 ms 8.07 MiB
random_00 AC 12 ms 8.16 MiB
random_01 AC 14 ms 8.05 MiB
random_02 AC 6 ms 8.07 MiB
random_03 AC 13 ms 8.16 MiB
random_04 AC 5 ms 8.07 MiB

#include<bits/extc++.h> #include<bits/stdc++.h> //#define clock chrono::steady_clock::now().time_since_epoch().count() //#define x() real() //#define y() imag() #define int long long //#define double long double using namespace std; using pii = pair<int, int>; using pll = pair<long long, long long>; using orderedSet = __gnu_pbds::tree<int, __gnu_pbds::null_type, less<int>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>; struct KM{ // Maximum Bipartite Weighted Matching (Perfect Match) static const int MAXN = 1000; const int INF = LLONG_MAX; //LL int px[MAXN],py[MAXN],match[MAXN],par[MAXN],n; int g[MAXN][MAXN],lx[MAXN],ly[MAXN],slack_y[MAXN]; // ^^^^ long long void init(int _n){ n = _n; for (int i=0; i<n; i++) for (int j=0; j<n; j++) g[i][j] = 0; } void add_edge(int x, int y, int w){ // LL g[x][y] = w; } void adjust(int y){ match[y]=py[y]; if(px[match[y]]!=-2) adjust(px[match[y]]); } bool dfs(int x){ for(int y=0;y<n;++y){ if(py[y]!=-1)continue; int t=lx[x]+ly[y]-g[x][y];//LL if(t==0){ py[y]=x; if(match[y]==-1){ adjust(y); return 1; } if(px[match[y]]!=-1)continue; px[match[y]]=y; if(dfs(match[y]))return 1; }else if(slack_y[y]>t){ slack_y[y]=t; par[y]=x; } } return 0; } int solve(){//LL fill(match,match+n,-1); fill(ly,ly+n,0); for(int i=0;i<n;++i){ lx[i]=-INF; for(int y=0;y<n;++y){ lx[i]=max(lx[i],g[i][y]); } } for(int i=0;i<n;++i){ for(int j=0;j<n;++j)slack_y[j]=INF; fill(px,px+n,-1); fill(py,py+n,-1); px[i]=-2; if(dfs(i))continue; bool flag=1; while(flag){ int cut=INF; //LL for(int j=0;j<n;++j) if(py[j]==-1)cut=min(cut,slack_y[j]); for(int j=0;j<n;++j){ if(px[j]!=-1)lx[j]-=cut; if(py[j]!=-1)ly[j]+=cut; else slack_y[j]-=cut; } for(int y=0;y<n;++y){ if(py[y]==-1&&slack_y[y]==0){ py[y]=par[y]; if(match[y]==-1){ adjust(y); flag=0; break; } px[match[y]]=y; if(dfs(match[y])){ flag=0; break; } } } } } int res=0;//LL for(int i=0;i<n;++i) res+=g[match[i]][i]; return res; } }graph; signed main() { ios::sync_with_stdio(false), cin.tie(NULL); int N; cin >> N; KM km; km.init(2 * N); for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) { int w; cin >> w; km.add_edge(i, j + N, 1000000000 - w); km.add_edge(j + N, i, 1000000000 - w); } cout << (2 * N * 1000000000 - km.solve()) / 2 << '\n'; for(int i = 0; i < N; i++) cout << km.match[i] - N << " \n"[i + 1 == N]; return 0; }