电商网站是获取流量,求个免费网站好人有好报,个人如何做公益网站,潮动九州网站建设正题
题目链接:https://www.luogu.com.cn/problem/P6628 题目大意
给出nnn个点的一张完全无向图#xff0c;i∼ji\sim ji∼j的边权是∣i−j∣|i-j|∣i−j∣。
然后给出mmm条必经边#xff0c;和起点sss。
求对于每个终点经过所有必经边的最短路径。 1≤n≤2500,0≤m≤n(n…正题
题目链接:https://www.luogu.com.cn/problem/P6628 题目大意
给出nnn个点的一张完全无向图i∼ji\sim ji∼j的边权是∣i−j∣|i-j|∣i−j∣。
然后给出mmm条必经边和起点sss。
求对于每个终点经过所有必经边的最短路径。
1≤n≤2500,0≤m≤n(n−1)21\leq n\leq 2500,0\leq m\leq \frac{n(n-1)}{2}1≤n≤2500,0≤m≤2n(n−1) 解题思路
很经典的模型首先起点和终点连一条边然后考虑加最少的边使得有欧拉回路。
欧拉回路有两个条件度数都是偶数很好满足直接把相邻的奇点连边肯定最优但是还需要满足连通的条件。
考虑到图上边权的特殊性我们显然只需要使用形如i∼i1i\sim i1i∼i1的边而这些边没有必要替代之前新加的边。所以直接拿这些边跑剩下连通块的最小生成树就好了。
时间复杂度O(mn2logn)O(mn^2\log n)O(mn2logn) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N2510;
struct edge{int x,y,w;
}e[N];
int n,m,s,cnt,ans,k,B[N*N];
int deg[N],fa[N],pf[N],b[N1];
int find(int x)
{return (fa[x]x)?x:(fa[x]find(fa[x]));}
void unionn(int x,int y){xfind(x);yfind(y);if(x!y)fa[x]y;return;
}
bool cmp(edge x,edge y)
{return x.wy.w;}
int main()
{scanf(%d%d%d,n,m,s);int sum0;for(int i1;in;i)fa[i]i;for(int i1,x,y;im;i){scanf(%d%d,x,y);unionn(x,y);deg[x];deg[y];B[cnt]x;B[cnt]y;sumabs(x-y);}B[cnt]s;sort(B1,B1cnt);cntunique(B1,B1cnt)-B-1;for(int i1;in;i)pf[i]find(i);deg[s];m0;for(int t1;tn;t){deg[t];anssum;int last0;for(int i1;icnt;i)b[i]B[i];kcnt;b[k]t;sort(b1,b1k);kunique(b1,b1k)-b-1;for(int i1;in;i)fa[i]pf[i];for(int i1;in;i)if(deg[i]1){if(last){for(int jlast;ji;j)unionn(i,j);ansi-last;last0;}else lasti;}for(int i1;ik;i)e[i](edge){b[i],b[i1],b[i1]-b[i]};sort(e1,ek,cmp);for(int i1;ik;i){int xfind(e[i].x),yfind(e[i].y);if(xy)continue;fa[x]y;anse[i].w*2;}printf(%d ,ans);deg[t]--;}return 0;
}
