結果

問題 No.519 アイドルユニット
ユーザー rgw2010
提出日時 2025-03-17 19:20:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 4,244 bytes
コンパイル時間 2,799 ms
コンパイル使用メモリ 204,788 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-17 19:20:06
合計ジャッジ時間 3,805 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi; 
#define maxn 4000005
#define inf 0x3f3f3f3f
#define N 805
int n,m;
struct edge{
    int u,v,w;
}e[N][N];
int lab[N],sl[N],q[N],hd,tl,rt[N],col[N],mat[N],frm[N][N],fa[N];
int vis[N],tim;
vi p[N];
int d(edge x){return lab[x.u]+lab[x.v]-e[x.u][x.v].w*2;}
void upd(int u,int v){if(!sl[v]||d(e[u][v])<d(e[sl[v]][v]))sl[v]=u;}
void updall(int u){
    sl[u]=0;
    For(i,1,n)if(e[i][u].w>0 && rt[i]!=u && col[rt[i]]==0) upd(i,u);
}
void push(int u){
    if(u<=n) q[++tl]=u;
    else for(int x:p[u]) push(x);
}
void setrt(int u,int r){
    rt[u]=r;
    if(u>n) for(int x:p[u]) setrt(x,r);
}
int rot(int b,int x){
    int pos=find(p[b].begin(),p[b].end(),x)-p[b].begin();
    if(pos%2==0)return pos;
    reverse(p[b].begin()+1,p[b].end());
    return p[b].size()-pos;
}
void match(int u,int v){
    mat[u]=e[u][v].v;
    if(u<=n)return;
    auto w=e[u][v];
    int x=frm[u][w.u],pos=rot(u,x);
    For(i,0,pos-1) match(p[u][i],p[u][i^1]);
    match(x,v);
    rotate(p[u].begin(),p[u].begin()+pos,p[u].end());
}
void aug(int u,int v){
    assert(u&&v);
    int t=rt[mat[u]];
    match(u,v);
    if(t) match(t,rt[fa[t]]),aug(rt[fa[t]],t);
}
int lca(int u,int v){
    ++tim;
    while(u||v){
        if(vis[u]==tim)return u;
        vis[u]=tim;
        u=rt[mat[u]];
        if(u)u=rt[fa[u]];
        if(!u)swap(u,v);
    }return 0;
}
int newn(){
    int x=n+1;
    while(x<=m&&rt[x])++x; if(x>m)++m;
    p[x].clear(),lab[x]=mat[x]=rt[x]=col[x]=0;
    return x;
}
void blossom(int u,int v,int r){
    int x=newn();
    mat[x]=mat[r];
    p[x].pb(r);
    for(int i=u;i!=r;i=rt[fa[i]]){
        p[x].pb(i),p[x].pb(i=rt[mat[i]]);
        push(i);
    }
    reverse(p[x].begin()+1,p[x].end());
    for(int i=v;i!=r;i=rt[fa[i]]){
        p[x].pb(i),p[x].pb(i=rt[mat[i]]);
        push(i); 
    }
    setrt(x,x);
    For(i,1,m)e[x][i].w=e[i][x].w=0,frm[x][i]=0;
    for(int t:p[x]){
        For(i,1,m){
            if(!e[x][i].w||d(e[t][i])<d(e[x][i]))
                e[x][i]=e[t][i],e[i][x]=e[i][t];
        }
        For(i,1,n)if(frm[t][i])frm[x][i]=t;
    }
    updall(x);
}
void expand(int x){
    for(int u:p[x]) setrt(u,u);
    int u=frm[x][e[x][fa[x]].u],pos=rot(x,u);
    for(int i=0;i<pos;i+=2){
        int a=p[x][i],b=p[x][i+1];
        fa[a]=e[b][a].u;
        col[a]=1,col[b]=0;
        sl[a]=0;
        updall(b),push(b);
    }
    col[u]=1;
    fa[u]=fa[x];
    for(int i=pos+1;i<p[x].size();++i)
        col[p[x][i]]=-1,updall(p[x][i]);
    rt[x]=0;
}
bool path(edge e){
    int u=rt[e.u],v=rt[e.v];
    assert(!d(e));
    if(col[v]==-1){
        fa[v]=e.u;
        col[v]=1;
        int t=rt[mat[v]];
        sl[v]=sl[t]=col[t]=0;
        push(t);
    }
    else if(!col[v]){
        int t=lca(u,v);
        if(!t)return aug(u,v),aug(v,u),1;
        else blossom(u,v,t);
    }
    return 0;
}
bool bfs()
{
    For(i,0,m) col[i]=-1,sl[i]=0;
    hd=1,tl=0;
    For(i,1,m)if(rt[i]==i&&!mat[i])fa[i]=col[i]=0,push(i);
    if(!tl)return 0;
    while(1){
        while(hd<=tl){
            int u=q[hd++];
            For(v,1,n)
                if(e[u][v].w>0&&rt[u]!=rt[v]){
                    if(d(e[u][v])) upd(u,rt[v]);
                    else if(path(e[u][v])) return 1; 
                }
        }
        int tmp=inf;
        For(i,1,n) if(col[rt[i]]==0) tmp=min(tmp,lab[i]);
        For(i,n+1,m) if(rt[i]==i && col[i]==1) tmp=min(tmp,lab[i]>>1);
        For(i,1,m) if(rt[i]==i && sl[i] && col[i]!=1) tmp=min(tmp,d(e[sl[i]][i])>>(col[i]+1));
        For(i,1,n){
            if(col[rt[i]]==0) lab[i]-=tmp;
            if(col[rt[i]]==1) lab[i]+=tmp;
            if(lab[i]<=0) return 0;
        }
        For(i,n+1,m){
            if(rt[i]==i){
                if(col[i]==0) lab[i]+=tmp*2;
                if(col[i]==1) lab[i]-=tmp*2;
            }
        }
        hd=1,tl=0;
        For(i,1,m)
            if(rt[i]==i && sl[i] && rt[sl[i]]!=i && !d(e[sl[i]][i]) && path(e[sl[i]][i])) return 1;
        For(i,n+1,m)
            if(rt[i]==i && col[i]==1 && !lab[i]) expand(i);
    }
}
signed main(){
//  freopen("group.in", "r", stdin);
//  freopen("group.out", "w", stdout);
    n=read(),m=n;
    int mx=0;
    For(i,1,n){
        For(j,1,n){
            int x = read();
            e[i][j] = (edge){i, j, x};
            frm[i][j] = 0;
            mx = max(mx, x);
        }
    }
    For(i,1,n)frm[i][i]=i;
    For(i,1,n)lab[i]=mx,rt[i]=i,p[i].clear();
    while(bfs());
    long long res=0;
    For(i,1,n)if(mat[i]&&i<mat[i])res+=e[i][mat[i]].w;
    cout<<res<<"\n";
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0