P2685 [TJOI2012]橋

xcxcli題解
下面思路仿照上述題解，代碼基本照抄上述題解

---

$u?v$表示$u$到$v$的最短路
$u\to v$表示$u$和$v$直接相連的邊
$d{1}_u$表示$1?u$的最短路
$d{n}_u$表示$n?v$的最短路

題意化簡(jiǎn)一下就是讓你求刪除一條邊使得$1?n$最大化，并求刪邊方案數(shù)。

首先不難發(fā)現(xiàn)，如果我們選擇刪除的邊不在$1?n$的路徑上，并不會(huì)對(duì)$1?n$的大小產(chǎn)生影響，也就是如果要產(chǎn)生影響必須刪除該路徑上的一條邊。

不妨假設(shè)$1?n$路徑上的點(diǎn)如下
$$1\to ?\to a\to b\to c\to d\to ?\to n$$
如果我們現(xiàn)在選擇刪除$b\to c$這條邊，發(fā)現(xiàn)這條路徑被切成兩部分$1\to ?\to a\to b$和$c\to d\to ?\to n$，由于我們現(xiàn)在已經(jīng)刪除$b\to c$這條邊，新的$1?n$一定是$1?x?u\to v?y?n$，并且$x\in 1\to ?\to a\to b,y\in c\to d\to ?\to n$

也就是我們現(xiàn)在讓其強(qiáng)制走一條不在$1?n$上的路徑即$u\to v$，并且走此路徑能夠避開(kāi)$b\to c$，$1?x?u\to v?y?n$路徑的權(quán)值顯然是$d{1}_u+w_{u\to v}+d{n}_v$，讓其更新刪除$b\to c$后$1?n$的最短路。

顯然我們不能枚舉$x,y$然后在枚舉$u\to v$去更新刪除$b\to c$的結(jié)果，有一個(gè)直接的想法就是$1?x?u\to v?y?n$路徑能夠避開(kāi)哪些$1\to ?\to a\to b\to c\to d\to ?\to n$的邊，假設(shè)它能夠避開(kāi)$a\to b\to c\to d$顯然這個(gè)結(jié)果能夠更新刪除$a\to b$或者$b\to c$或者$c\to d$的答案。

于是我們只需要枚舉$u\to v$這條邊（需要保證此邊不在$1?n$的路徑上），然后找到$1?x?u\to v?y?n$能夠避開(kāi)哪些邊（仔細(xì)想想可知避開(kāi)的路徑一定是連續(xù)的），進(jìn)行區(qū)間更新（線段樹(shù)）即可。
這也是上述博客預(yù)處理$L_u$和$R_u$的原因！！！

有了上述兩個(gè)數(shù)組那么$1?x?u\to v?y?n$避開(kāi)的路徑則是$L_u?R_v$之間的邊。

dengyaotriangle詳細(xì)證明

#include<queue> #include<cstring> #include<iostream> #include<algorithm> using namespace std; using pii=pair<int,int>; constexpr int N=100010,M=400010; constexpr int INF=0x3f3f3f3f; int h[N],e[M],ne[M],w[M],idx; void add(int a,int b,int c){e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;} int n,m; bool st[N]; int d1[N],dn[N]; int path[N],cnt,id[N]; bool in[M]; int L[N],R[N],ans[N]; void dijkstra(int S,int d[]) {memset(d,0x3f,(n+1)*sizeof(int));memset(st,0,sizeof st);d[S]=0;priority_queue<pii,vector<pii>,greater<pii> >q;q.push({0,S});while(q.size()){int u=q.top().second;q.pop();if(st[u]) continue;st[u]=1;for(int i=h[u];i!=-1;i=ne[i]){int v=e[i];if(d[v]<=d[u]+w[i]) continue;d[v]=d[u]+w[i];q.push({d[v],v});}} } void bfs(int k,int d[],int f[]) {queue<int> q;q.push(path[k]);f[path[k]]=k;while(q.size()){int u=q.front();q.pop();for(int i=h[u];i!=-1;i=ne[i]){int v=e[i];if(!id[v]&&!f[v]&&d[u]+w[i]==d[v]) f[v]=k,q.push(v);}} } struct node {int l,r,v; }tree[N<<2]; void build(int u,int l,int r) {tree[u]={l,r,INF};if(l==r) return;int mid=l+r>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r); } void modify(int u,int l,int r,int x) {if(tree[u].l>=l&&tree[u].r<=r) return tree[u].v=min(tree[u].v,x),void();int mid=tree[u].l+tree[u].r>>1;if(l<=mid) modify(u<<1,l,r,x);if(r>mid) modify(u<<1|1,l,r,x); } void pushdown(int u) {if(tree[u].l==tree[u].r){ans[tree[u].l]=tree[u].v;return;}tree[u<<1].v=min(tree[u<<1].v,tree[u].v);tree[u<<1|1].v=min(tree[u<<1|1].v,tree[u].v);int mid=tree[u].l+tree[u].r>>1;pushdown(u<<1),pushdown(u<<1|1);} int main() {cin>>n>>m;memset(h,-1,sizeof h);for(int i=1;i<=m;i++){int a,b,c;cin>>a>>b>>c;add(a,b,c),add(b,a,c);}dijkstra(1,d1),dijkstra(n,dn);// 預(yù)處理1->n路徑上的點(diǎn)int u=1;while(u!=n){path[++cnt]=u;id[u]=cnt;for(int i=h[u];i!=-1;i=ne[i]){int v=e[i];if(dn[v]+w[i]==dn[u]) {in[i]=1;u=v;break;}}}path[++cnt]=n;id[n]=cnt;//1->n路徑上的點(diǎn) for(int i=1;i<=cnt;i++) bfs(i,d1,L),bfs(i,dn,R);--cnt;build(1,1,cnt);//我們將1->n路徑上的邊編號(hào)for(int u=1;u<=n;u++)for(int i=h[u];i!=-1;i=ne[i]){int v=e[i];if(!in[i]&&L[u]<R[v])// L[u]->R[v]邊的編號(hào)是L[u]->R[v]-1modify(1,L[u],R[v]-1,d1[u]+w[i]+dn[v]);}pushdown(1);int mx=0,res=0;for(int i=1;i<=cnt;i++){if(mx<ans[i]) mx=ans[i],res=1;else if(mx==ans[i]) res++;}if(mx==d1[n]) res=m;cout<<mx<<' '<<res<<'\n'; }

總結(jié)

以上是生活随笔為你收集整理的P2685 [TJOI2012]桥（最短路+线段树）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。