图论、贪心好题。
枚举每一个朋友,设一个朋友从 \(s\) 出发,到 \(t\) 结束。那么如果用边来表示其行动轨迹,必然是 \(s,t\) 有奇数度,其它点均为偶数度。如果在 \(s,t\) 之间连一条边,我们只要找到一种连边的方式使得每个点都是偶数度就可以了。容易知道如果每个点都是偶数度并且 \(s,t\) 连通,这两点之间必然存在一条合法路径。
开有丁香花的道路必须经过,所以先把这些边连上。现在我们的目的是:花最小的代价连边,使得每一个点的度数为偶数,并且确保 \(s,t\) 和 所有 的边连通。
这个时候就要想一种贪心策略。我们首先保证每个点的度数为偶数,可以在遇到一个点的度数为奇数时,把它与后面第一个度数为奇数的点之间连边。因为每一条边都会贡献两个度数,所以最终一定能使得每一个点的度数均为偶数。但是在确保连通性的情况下有一个更优策略:把度数为奇数的点直接向下一个点连边。这样边权和没有改变,但是连通了更多的点。
确保所有边连通,则可以把所有连通块缩点后跑最小生成树。
最后是计算贡献。因为最小生成树建出来后要保证度数,所以最小生成树的边要取两倍。建图时只需要保证相邻的连通块之间有最小边,就可以保证最优。代码中给出了一种较为简易的实现方式。
代码如下:
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int N=2505;
int n,m,s,ind[N],iid[N],fa[N],ffa[N];ll sum,ans;
struct Edge{int u,v,w;};vector<Edge>e;
bool operator<(const Edge&A,const Edge&B){return A.w<B.w;}
int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}
inline void merge(int x,int y){fa[get(x)]=get(y);}
int main(){
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);sum+=abs(u-v);
iid[u]++;iid[v]++;merge(u,v);
}
for(int i=1;i<=n;i++)ffa[i]=fa[i];
for(int t=1;t<=n;t++){
for(int i=1;i<=n;i++)fa[i]=ffa[i],ind[i]=iid[i];
ind[s]++;ind[t]++;merge(s,t);ans=0;
for(int i=1;i<=n;i++)if(ind[i]&1){
ind[i]++;ind[i+1]++;merge(i,i+1);ans++;
}
e.clear();
for(int i=1,j=0;i<=n;i++)if(ind[i]){
if(j&&get(i)!=get(j))e.push_back({j,i,i-j});
j=i;
}
sort(e.begin(),e.end());
for(Edge E:e){
if(get(E.u)!=get(E.v))merge(E.u,E.v),ans+=(E.w<<1);
}
printf("%lld ",ans+sum);
}
return 0;
}
标签:度数,连边,连通,一个点,P6628,题解,奇数,偶数,联考
From: https://www.cnblogs.com/hihihi198/p/16882089.html