首页 > 代码库 > sgu-206 Roads
sgu-206 Roads
题目大意:
给你一个n,m,表示一个无向图G中有n个点,m条边,m>=n-1,然后保证前n-1条边可以构成一棵生成树,然后问对于每条边应该如何修改权值使得前n-1条边构成的生成树是图的最小生成树。输出每条边修改后的值
解题思路:
首先想了很久都没有思路,然后最后怂了,看了别人的题解才发现这么神奇,这题的正解是KM
观察题目我们发现,对于前n-1条边,我们需要的就是将其改小,对于n-1条边之后的边,我们需要的是将其改大,我们知道,对于一条不在生成树上的边k2<u,v>,它如果不能改变最小生成树的话需要满足树上u->v的路径上的任意一条边k1<i,j>有w‘[k1]<=w‘[k2](此处是指修改后的),假设第i条边的变化量为change[i],那么也就是说有w[k1]-change[k1]<=w[k2]+change[k2] => w[k1]-w[k2]<=change[k1]+change[k2]
我们发现如果要变化最小的话就有w[k1]-w[k2]=change[k1]+change[k2]这就是KM的条件啊
仔细观察一下这个式子,是不是很像km的w[i][j]<=gx[i]+gy[j],由于当时我们的KM是我讲的,所以我一下就明白了,那么我们可以把每一条边作为一个节点,前 n-1条边设为x节点,后面的边设为y节点,然后将两边的节点补到相同,x与y如果在原图没有边的话就连0边,如何算作有边呢?
就是对于一条不在生成树上的边k2<u,v>,在生成树上u->v的路径上的任意一条边k1<i,j>,我们就在x[k1]与y[k2]间连一条权值为w[k1]-w[k2]的边。之后直接跑一边KM就行了。。。
AC代码:
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> #define MAX(a,b) ((a)>(b)?(a):(b)) #define MIN(a,b) ((a)>(b)?(b):(a)) using namespace std; int a[510]={0},b[510]={0},z[501]={0}; int g[510][510]={{0}}; int x[510]={0},y[510]={0}; int w[510][510]={{0}}; int slack[510]={0}; int n,m; int hashx[510]={0}; int hashy[510]={0}; int father[510]={0}; bool find(int k) { hashx[k]=1; for(int i=1;i<=m;i++) { if(hashy[i]==0 && w[k][i]==x[k]+y[i]) { hashy[i]=1; if(father[i]==0 || find(father[i])==1) { father[i]=k; return true; } } else slack[i]=MIN(slack[i],x[k]+y[i]-w[k][i]); } return false; } void km() { for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) x[i]=MAX(w[i][j],x[i]); for(int i=1;i<=m;i++) { memset(slack,0x3f3f3f3f,sizeof(slack)); for(;;) { int d=2e9; memset(hashx,0,sizeof(hashx)); memset(hashy,0,sizeof(hashy)); if(find(i)==1) break; for(int i=1;i<=m;i++) if(hashy[i]==0) d=MIN(d,slack[i]); for(int i=1;i<=m;i++) { if(hashx[i]==1) x[i]-=d; if(hashy[i]==1) y[i]+=d; else slack[i]-=d; } } } return; } bool dfs(int father,int u,int v,int k) { if(u==v) return true; for(int i=1;i<=n;i++) { if(i==father || g[u][i]==0) continue; if(dfs(u,i,v,k)==1) { w[g[u][i]][k]=z[g[u][i]]-z[k]; return true; } } return false; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i],&b[i],&z[i]); for(int i=1;i<n;i++) g[a[i]][b[i]]=g[b[i]][a[i]]=i; for(int i=n;i<=m;i++) dfs(0,a[i],b[i],i); km(); for(int i=1;i<n;i++) printf("%d\n",z[i]-x[i]); for(int i=n;i<=m;i++) printf("%d\n",z[i]+y[i]); return 0; }
sgu-206 Roads