JX CSP 游寄：是时候退役了。

· · 生活·游记

CSP-J

T1，很简单，唯一的坑（全是 0 要只输出一个零，也保证没有了）。

T2，推了下公式，但是不知道有没有错，样例过了。

T3，二分和贪心（区间覆盖），样例都过了。

T4，打了暴力。

CSP-S

T1，一眼出来的贪心。

T2，打了特殊性质，还打了暴力枚举哪个农村选，那个农村不选，就是没有想到可以提前跑一次。

T3，全输出 0，题目看不懂。

T4，暴力 dfs，大概对 1,2 两个点吧。

总分预计 [140,156]，预计没有一等，要退役了。

十一月二号更新：
代码发下来了，通过民间自测测得如下分数。
洛谷自测 177。
核桃 OJ 自测 180。

:::info[让我们欣赏一下 S 组 T2 的超绝代码]

#include<bits/stdc++.h>
using namespace std;
#define LL long long 
#define ull unsigned long long
//#define connect_or_leave_oi return
int n,m,k;
struct node{
    int u,v;
    LL w;
    int id;
    friend bool operator <(node x,node y){
        return x.w<y.w;
    }
};
vector<node>tu;
const int N=1e5+100;
LL c[15];
int father[N];
int find_father(int x){
    return father[x]==x?x:father[x]=find_father(father[x]);
}
int bj[12];
vector<int>rem_id[12];
LL a[12][N];
int gx[12];
LL ans=LONG_LONG_MAX;
void tsxz(){
    for(int i=1;i<=n+k+10;i++)father[i]=i;
    for(int i=1;i<=k;i++){
        //tu.push_back({0,n+i,c[i]});
        for(int j=1;j<=n;j++){
            tu.push_back({n+i,j,a[i][j]});
        }
    }
    sort(tu.begin(),tu.end());
    for(int i=1;i<=n+k+10;i++)father[i]=i;
    int len=tu.size();
    ans=0;
    for(int i=0;i<len;i++){
        int u=tu[i].u;
        int v=tu[i].v;
        int l=find_father(u),r=find_father(v);
        if(l==r)continue;
        ans+=tu[i].w;
        father[l]=father[r];
    }
    return;
}
LL kls(vector<node>tu,LL sum,int cn){
    sort(tu.begin(),tu.end());
    LL an=sum;
    for(int i=1;i<=n+k+10;i++)father[i]=i;
    int len=tu.size(),cnt=0;
    for(int i=0;i<len;i++){
        int u=tu[i].u;
        int v=tu[i].v;
        if(cnt==n+cn-1)break;
        if(an>=ans)break;
        int l=find_father(u),r=find_father(v);
        if(l==r)continue;
        an+=tu[i].w;cnt++;
        father[l]=father[r];
    }
    return an;
}
void dfs(int now,vector<node>tu,bool yes,LL sum,int cnt){
    if(yes){
        sum+=c[now];
        for(int i=1;i<=n;i++){
            tu.push_back({n+now,i,a[now][i]});
        }
    }
    if(now==k){
        ans=min(ans,kls(tu,sum,cnt));return;
    }
    dfs(now+1,tu,1,sum,cnt+1);
    dfs(now+1,tu,0,sum,cnt);
    return;
}
void tscl(){
    for(int i=1;i<=n+k;i++)father[i]=i;
    LL ans2=0;
    for(int i=1;i<=k;i++){
        for(int j=1;j<=n;j++){
            tu.push_back({n+i,j,c[i]+a[i][j]});
        }
    }
    sort(tu.begin(),tu.end());int len=tu.size();
    for(int i=0;i<len;i++){
        if(tu[i].u>n)rem_id[tu[i].u-n].push_back(i);
    }
    for(int i=0;i<len;i++){
        int u=tu[i].u;
        int v=tu[i].v;
        int l=find_father(u),r=find_father(v);
        if(l==r)continue;
        ans2+=tu[i].w;
        father[l]=father[r];
        if(u>n&&v!=0){
            bj[u-n]++;
            gx[u-n]+=tu[i].w;
            if(bj[u-n]==1){
                for(int j=0;j<n;j++){
                    tu[rem_id[u-n][j]].w-=c[u-n];
                }
                sort(tu.begin(),tu.end());
            }
        }
    }
    for(int i=1;i<=k;i++){
        if(bj[i]<2)ans2-=gx[i];
    }
    ans=ans2;
    return;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    freopen("road.in","r",stdin);
    freopen("road.out","w",stdout);
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        int u,v;
        LL w;
        cin>>u>>v>>w;
        tu.push_back({u,v,w});
    }
    //sort(tu.begin(),tu.end());
    //LL ans1=0;
    //for(int i=0;i<len;i++){
    //  int u=tu[i].u;
    //  int v=tu[i].v;
    //  int l=find_father(u),r=find_father(v);
    //  if(l==r)continue;
    //  ans1+=tu[i].w;
    //  father[l]=father[r];
    //}
    bool ok=1;
    for(int i=1;i<=k;i++){
        cin>>c[i];
        if(c[i]!=0)ok=0;
        //tu.push_back({0,n+i,c[i]});
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
            //tu.push_back({n+i,j,w+c[i]});
        }
    }
    if(!ok){
        if((k>=5&&n>=1000&&m>=1000000))tscl();
        else dfs(0,tu,0,0,0);
    }
    else tsxz();
    cout<<ans;
    //connect_or_leave_oi 0;
    return 0;
}

:::