Submit Info #44599

Problem Lang User Status Time Memory
Assignment Problem cpp ZigZagKmp AC 57 ms 2.64 MiB

ケース詳細
Name Status Time Memory
example_00 AC 0 ms 0.71 MiB
hand_minus_00 AC 57 ms 2.55 MiB
hand_plus_00 AC 56 ms 2.64 MiB
max_random_00 AC 28 ms 2.55 MiB
max_random_01 AC 25 ms 2.55 MiB
max_random_02 AC 25 ms 2.55 MiB
max_random_03 AC 28 ms 2.59 MiB
max_random_04 AC 29 ms 2.57 MiB
random_00 AC 3 ms 1.43 MiB
random_01 AC 7 ms 1.43 MiB
random_02 AC 1 ms 0.96 MiB
random_03 AC 4 ms 1.37 MiB
random_04 AC 1 ms 0.80 MiB

#include<bits/stdc++.h> using namespace std; #define maxn 505 #define maxm 2000005 #define inf 0x3f3f3f3f3f3f3f3fll #define linf 0x3f3f3f3f3f3f3f3fll #define int long long #define ull unsigned long long #define db double #define ldb long double #define mod 1000000007 #define eps 1e-9 #define local void file(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);} template <typename Tp> void read(Tp &x){ int fh=1;char c=getchar();x=0; while(!isdigit(c)){if(c=='-'){fh=-1;}c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c&15);c=getchar();}x*=fh; } int n,m; int W[505][505]; int va[maxn],vb[maxn],la[maxn],lb[maxn]; int ma[maxn],mb[maxn],pre[maxn]; int ans,dlt[maxn]; void rev(int x){ for(int lst;x;x=lst){ lst=ma[pre[x]]; ma[pre[x]]=x,mb[x]=pre[x]; } } void KM(int S){ memset(va,0,sizeof(va)); memset(vb,0,sizeof(vb)); memset(dlt,0x3f,sizeof(dlt)); queue<int>q; q.push(S); while(1){ while(!q.empty()){ int x=q.front();q.pop(); va[x]=1; for(int y=1;y<=n;++y){ if(!vb[y]){ if(la[x]+lb[y]==W[x][y]){ vb[y]=1;pre[y]=x; if(!mb[y]){rev(y);return;} q.push(mb[y]); } else{ if(dlt[y]>(la[x]+lb[y]-W[x][y])){ dlt[y]=la[x]+lb[y]-W[x][y]; pre[y]=x;//? } } } } } int d=linf; for(int i=1;i<=n;++i)if(!vb[i])d=min(d,dlt[i]); if(d==linf)return; for(int i=1;i<=n;++i)if(va[i])la[i]-=d; for(int i=1;i<=n;++i){ if(vb[i])lb[i]+=d; else dlt[i]-=d; } for(int i=1;i<=n;++i){ if(!vb[i]&&dlt[i]==0){ vb[i]=1; if(!mb[i]){rev(i);return;} q.push(mb[i]); } } } } signed main(){ read(n); for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ read(W[i][j]);W[i][j]=-W[i][j]; } } for(int i=1;i<=n;++i)la[i]=-inf,lb[i]=0; for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ la[i]=max(la[i],W[i][j]); } } for(int i=1;i<=n;++i){ KM(i); } for(int i=1;i<=n;++i)ans+=W[mb[i]][i]; printf("%lld\n",-ans); for(int i=1;i<=n;++i)printf("%lld ",ma[i]-1); return 0; }