当前位置：首页 > news >正文

oi 卡时技巧

news 2026/5/12 5:21:15

这篇记录一下卡时技巧

卡时就是指在程序即将t飞的时候直接输出当前答案，适合在答案更新过程中当前答案有对的可能，但是全部更新完时间不够，就在即将t飞的时候结束程序，直接输出当前答案。

具体代码示例1：

//来源于wlh__1的爆改xu-yiming卡时代码
//csp 2025 t2
#include<bits/stdc++.h>
#define inf 1e18 
using namespace std;
typedef long long LL;
const int N=1e4+50,M=1e6+10;int n,K;
struct edge{int w,a,b;
};
vector<edge> tmp;
vector<edge> mp;
int wp[12][N];
bool checkA(){for(int i=1;i<=K;i++){if(wp[i][0]) return 0;}return 1;
}
bool cmp(edge a,edge b){return a.w<b.w;
}
int fa[N];
int find(int x){if(x==fa[x]) return x;return fa[x]=find(fa[x]);
}
LL cl(int st){LL ans=0;mp=tmp;for(int i=1;i<=K;i++){if((st>>i-1)&1){ans+=wp[i][0];for(int j=1;j<=n;j++){mp.push_back({wp[i][j],i+n,j});}		}}sort(mp.begin(),mp.end(),cmp);for(int i=1;i<=n+K;i++) fa[i]=i;for(int i=0;i<mp.size();i++){int a=mp[i].a,b=mp[i].b,w=mp[i].w;a=find(a);b=find(b);if(a==b) continue;ans+=w;fa[a]=b;}return ans;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int m;cin>>n>>m>>K;while(m--){int a,b,c;cin>>a>>b>>c;mp.push_back({c,a,b});}tmp=mp;for(int i=1;i<=K;i++){for(int j=0;j<=n;j++) cin>>wp[i][j];}if(checkA()){LL ans=cl((1<<K)-1);cout<<ans<<"\n";return 0;}LL ans=inf;for(int st=0;st<(1<<K) && double(clock())/CLOCKS_PER_SEC<=0.9;st++) ans=min(ans,cl(st));cout<<ans<<"\n";return 0;
}

在代码的倒数第五行即以下代码