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

NOIP2025模拟1

news 2026/3/27 4:01:16

T1：公司的供应链（dag）

思路：

大概就是推出性质但是没写出来。

我们不难发现，对于一个环来说，把环内全部的边删掉是合法的。

然后我们就从一个点开始搜，如果没有环，就把经过的边都标记一下，这是要保留的。然后再记录一下走过的边数，保证每个环只经过一次。

代码：

$code$

#include<iostream>
#include<vector>
using namespace std;
const int N=600000+5;
int n,m,cnt[N],f[N],x[N],y[N],ans;
bool vis[N];
vector<pair<int,int>> v[N];
inline int dfs(int x){if(vis[x]) return x;//有环 vis[x]=1;while(cnt[x]<(int)v[x].size()){int flag=dfs(v[x][cnt[x]].second);if(!flag) f[v[x][cnt[x]].first]=-1;//标记保留的边 cnt[x]++;//走过的边数 if(flag!=x&&flag){//后面有个小环 vis[x]=0;return flag;}}vis[x]=0;return 0;//无环 
}
int main(){
//	freopen("dag.in","r",stdin);
//	freopen("dag.out","w",stdout);ios::sync_with_stdio(false);cin>>n>>m;for(int i=1;i<=m;i++){cin>>x[i]>>y[i];v[x[i]].push_back(make_pair(i,y[i]));//建边 }for(int i=1;i<=n;i++) if(cnt[i]<(int)v[i].size()) dfs(i);//还有边没走 for(int i=1;i<=m;i++) if(f[i]==-1) ans++;cout<<ans<<'\n';for(int i=1;i<=m;i++) if(f[i]==-1) cout<<x[i]<<" "<<y[i]<<'\n';return 0;
}

T2：宇宙的卷积（juanji）

思路：

大概就是赛时两眼一闭数组就开 $20$ 然后挂了 $60 ~ pts$ 吧。

有没有大佬给我讲讲 $T2$ 啊！！真的不会啊！！

T3：舰队的远征（far）

思路：

看眼式子有点像李超，但是马上自我否定了。最后选择跑了 $n^2$ 遍 $dij$ 。

其实就是把路径分为三部分：

\[s→x=>y→t \]

$x,y$ 之间的边是我们新建的特殊边。

怎么求答案呢？

正着跑一边最短路求出到 $s$ 的最短路，反着求一遍最短路到 $t$ 的最短路，然后维护一下 $(x-y)^2$ 。

然后答案是什么呢？

\[dis1_x+dis2_y+(x-y)^2 \]

整理一下，可得

\[dis1_x+x^2+dis2_y+y^2-2*x*y \]

我们枚举每一个 $x$ ，因此 $dis1_x+x^2$ 为定制，所以我们只需要维护 $dis2_y+y^2-2*x*y$ 就好了。

用什么维护呢？用我否定了的李超线段树。【对不起】

然后呢？

然后就没了。

感谢 Wx_y大侠的博客（就是能不能换个题目🥺）

代码：

$code$

#include<iostream>
#include<queue>
#define int long long
using namespace std;
const int N=2e6+5,inf=1e18;
int n,m,s,t,x,y,z,dis1[N],dis2[N],ans=1e18,cnt1,cnt2,head1[N],head2[N],tr[N<<1];
bool vis1[N],vis2[N];
struct flower{int to,nxt,val;
}a[N],b[N];
struct css{int k,b;
}line[N];
inline void add1(int x,int y,int z){a[++cnt1].to=y;a[cnt1].val=z;a[cnt1].nxt=head1[x];head1[x]=cnt1;
}
inline void add2(int x,int y,int z){b[++cnt2].to=y;b[cnt2].val=z;b[cnt2].nxt=head2[x];head2[x]=cnt2;
}
inline void dij1(int s){priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;	for(int i=1;i<=n;i++) dis1[i]=1e18,vis1[i]=0;dis1[s]=0;q.push({0,s});while(!q.empty()){int x=q.top().second;q.pop();if(vis1[x]) continue;vis1[x]=1;for(int i=head1[x];i;i=a[i].nxt){int y=a[i].to;if(dis1[y]>dis1[x]+a[i].val){dis1[y]=dis1[x]+a[i].val;if(!vis1[y]) q.push(make_pair(dis1[y],y));}}}
}
inline void dij2(int s){priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;for(int i=1;i<=n;i++) dis2[i]=1e18,vis2[i]=0;dis2[s]=0;q.push({0,s});while(!q.empty()){int x=q.top().second;q.pop();if(vis2[x]) continue;vis2[x]=1;for(int i=head2[x];i;i=b[i].nxt){int y=b[i].to;if(dis2[y]>dis2[x]+b[i].val){dis2[y]=dis2[x]+b[i].val;if(!vis2[y]) q.push(make_pair(dis2[y],y));}}}
}
inline int calc(int id,int x){return line[id].k*x+line[id].b;
} 
inline void insert(int rt,int l,int r,int id){if(!tr[rt]){tr[rt]=id;return ;}if(l==r){if(calc(tr[rt],l)>calc(id,l)) tr[rt]=id;return ;}int mid=(l+r)>>1;if(calc(id,mid)<calc(tr[rt],mid)) swap(id,tr[rt]);if(calc(id,l)<calc(tr[rt],l)) insert(rt<<1,l,mid,id);if(calc(id,r)<calc(tr[rt],r)) insert(rt<<1|1,mid+1,r,id);
}
inline int query(int rt,int l,int r,int x){if(l==r) return calc(tr[rt],x);int ans=calc(tr[rt],x);int mid=(l+r)>>1;if(x<=mid) ans=min(ans,query(rt<<1,l,mid,x));else ans=min(ans,query(rt<<1|1,mid+1,r,x));return ans;
}
signed main(){freopen("far.in","r",stdin);freopen("far.out","w",stdout);ios::sync_with_stdio(false);cin>>n>>m>>s>>t;for(int i=1;i<=m;i++){cin>>x>>y>>z;add1(x,y,z);add2(y,x,z);}dij1(s);dij2(t);line[0]=(css){0,inf};for(int i=1;i<=n;i++) line[i]=(css){-2*i,i*i+dis2[i]};for(int i=1;i<=n;i++) insert(1,1,n,i);for(int i=1;i<=n;i++) ans=min(ans,query(1,1,n,i)+i*i+dis1[i]);cout<<ans<<'\n';return 0;
}