『模拟赛』暑假集训CSP提高模拟21
终于没RE了！不枉我辛辛苦苦调了几个小时...(
但是暴力没打完...(逃
T1 黎明与萤火
DFS序乱糊+贪心
注意要先消除叶子结点。
Elaina's Code
int n,fa[N],rdeg[N],hd[N],idx,ans[N],cnt;
bool vis[N];
stack<int> sta;
struct EDGE{
int nxt,to;
}e[N<<1];
void add(int x,int y){
e[++idx]=(EDGE){hd[x],y};
hd[x]=idx;
}
void dfs(int x,int f){
fa[x]=f;
sta.push(x);
for(int i=hd[x];i;i=e[i].nxt){
int to=e[i].to;
if(to==f) continue;
dfs(to,x);
}
}
void dfs2(int x){
vis[x]=1;
ans[++cnt]=x;
for(int i=hd[x];i;i=e[i].nxt){
int to=e[i].to;
--rdeg[to];
if(to==fa[x] || vis[to]) continue;
if(!(rdeg[to]&1)) dfs2(to);
}
}
signed main(){
n=rd;
for(int i=1;i<=n;i++){
int x=rd;
if(x){
add(i,x),add(x,i);
++rdeg[i],++rdeg[x];
}
}
dfs(1,0);
while(!sta.empty()){
int k=sta.top();
sta.pop();
if(!(rdeg[k]&1)) dfs2(k);
}
if(cnt==n){
puts("YES");
for(int i=1;i<=cnt;i++){
printf("%lld\n",ans[i]);
}
}else{
puts("NO");
}
return Elaina;
}
T2 Darling Dance
之前刷题好像刷到过一个类似的？但还是调了我好久...................... \(\ :(((((((((((((((((((((\)
赛时思路不是很清晰，简直一通乱维护...
贪心搞了搞，若当前答案集合的大小小于 \(K\) 且优先队列非空，则继续优先队列遍历，每次把一条边加入到答案集合中...
Elaina's Code
int hd[N],n,m,k,pre[N],vis[N],idx=1;
struct node{
int nxt,to,w;
}e[N<<1];
inline void add(int x,int y,int w){
e[++idx]=node{hd[x],y,w};
hd[x]=idx;
}
int dis[N];
vector<int> ans;
priority_queue<pair<int,int> > q;
void dij(){
for(int i=1;i<=n;i++) dis[i]=inf,vis[i]=0;
dis[1]=0;
q.push(make_pair(0,1));
while(!q.empty()&&ans.size()<k){
int u = q.top().second;
q.pop();
if(vis[u]) continue;
if(u^1) ans.push_back(pre[u]/2);
vis[u]=1;
for(int i=hd[u];i;i=e[i].nxt){
int to=e[i].to,w=e[i].w;
if(dis[to]>dis[u]+w){
dis[to]=dis[u]+w;
pre[to]=i;
q.push(make_pair(-dis[to],to));
}
}
}
}
signed main(){
// freopen("T2.in","r",stdin);
// freopen("out.out","w",stdout);
n=rd,m=rd,k=rd;
for(int i=1;i<=m;i++){
int x=rd,y=rd,w=rd;
add(x,y,w),add(y,x,w);
}
dij();
k=ans.size();
printf("%lld\n",k);
for(int i=0;i<k;i++)
printf("%lld ",ans[i]);
return Elaina;
}
其实这是一个最短路径树(SPT)的板子，由于 SPT 只需要 \(n−1\) 条边，我们删边只需要留下 \(min(k,n−1)\) 条边就行。
Dijkstra 跑完后 dfs 判断是否为 SPT 上的边并输出就行。不过 \(k=0\) 要特判。
Elaina's Code
int n,m,k,cnt;
int hd[N],idx;
struct EDGE{
int nxt,to,w;
}e[N];
int dis[N],pre[N];
bool vis[N];
struct node{
int to,w;
bool operator < (const node& a)const{
return w>a.w;
}
};
priority_queue<node>q;
inline void add(int x,int y,int z){
e[++idx]=(EDGE){hd[x],y,z};
hd[x]=idx;
}
void dij(int s){
memset(dis,0x7f,sizeof dis);
dis[s]=0;
q.push((node){s,0});
while(!q.empty()){
int u=q.top().to;q.pop();
if(vis[u])continue;
vis[u]=1;
for(int i=hd[u];i;i=e[i].nxt){
int to=e[i].to;
if(dis[to]>=dis[u]+e[i].w){
dis[to]=dis[u]+e[i].w;
q.push((node){to,dis[to]});
pre[to]=i;
}
}
}
}
void dfs(int u){
for(int i=hd[u];i;i=e[i].nxt){
int to=e[i].to;
if(i==pre[to]){
++cnt;
if(cnt>k||cnt==n) exit(0);
printf("%lld ",i+1>>1);
dfs(to);
}
}
}
signed main(){
n=rd,m=rd,k=rd;
for(int i=1;i<=m;++i){
int a,b,c;
a=rd,b=rd,c=rd;
add(a,b,c),add(b,a,c);
}
dij(1);
printf("%lld\n",k>n-1?n-1:k);
dfs(1);
return 0;
}
T3 Non-breath oblige
亖了。
看什么看，暴力打挂了不行吗？
T4 妄想感伤代偿联盟
我看你是在妄想。
图
翻到一张 罕见 莲莲的图
