用织梦软件如何做网站/百度竞价关键词怎么优化

Description

给出一张n个点，m条边的图，你可以选择一些边，使得1和n,2和n-1,3和n-2…k和n-k+1联通。代价为这些边的边权和。
求最小代价。
n<=10000，m<=12000，k<=4

Solution

这是一种神奇的方（shui）法。
（已经被打了一波脸~(>_<)~）图样图森破
如果只有一对点，那么答案就是他们的最短路。
如果多了一对点呢？
先选择一对跑最短路，然后把经过的边的边权变成0，然后再跑一边。
依次类推。
那么，我们只需要搜出顺序，然后使用玄学算法（我喜欢）。
怎么水过去的呀！！！

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a) for(int i=last[a];i;i=next[i])
#define N 10005
using namespace std;
const int inf=0x7fffffff;
bool f[5],bz[N],e[N*2];
int n,m,k,x,y,z,l,sum,ans,d[5],q[N*5],dis[N],p[N];
int t[N*2],next[N*2],v[N*2],last[N];
void add(int x,int y,int z) {t[++l]=y;v[l]=z;next[l]=last[x];last[x]=l;
}
void spfa(int S,int T) {memset(dis,127,sizeof(dis));int mx=dis[S];dis[S]=0;memset(bz,0,sizeof(bz));bz[S]=1;int i=0,j=1;q[1]=S;while (i<j) {rep(k,q[++i]) {int w=v[k];if (e[k]) w=0;if (dis[t[k]]>dis[q[i]]+w) {dis[t[k]]=dis[q[i]]+w;p[t[k]]=k;if (!bz[t[k]]) bz[t[k]]=1,q[++j]=t[k];}}bz[q[i]]=0;}if (dis[T]!=mx) sum+=dis[T];else sum=-1;
}
void find(int S,int T){for(int i=T;i!=S;i=t[p[i]^1]) e[p[i]]=e[p[i]^1]=1;
}
void permutation(int x) {if (x>k) {sum=0;memset(e,0,sizeof(e));fo(i,1,k) {spfa(d[i],n-d[i]+1);if (sum==-1) break;find(d[i],n-d[i]+1);}if (sum==-1) return;ans=min(ans,sum);}fo(i,1,k) if (!f[i]) {f[i]=1;d[x]=i;permutation(x+1);f[i]=0;}
}
int main() {scanf("%d%d%d",&n,&m,&k);l=1;fo(i,1,m) scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z);ans=inf;permutation(1);if (ans==inf) printf("-1");else printf("%d",ans);
}