[SGU206 Roads]KM算法的妙用

【题目大意】

给定N个城市和M条道路，其中前N-1条道路是大路，其它都是小路，并保证大 路可构成N个城市 的生成树。

第i条路费用为c_i，要求你谎报费用（设第i条路上报的费用为d_i），使得对费用数组d来说，N-1条大路恰为最小生成树，并且sum|c_i-d_i|尽可能小。

（摘自：http://crfish.blogbus.com/logs/62846336.html）

【算法分析】

本题的解题报告来自：http://wenku.baidu.com/view/7bfaa802de80d4d8d15a4faf.html

大概是这样：

令w[i]表示第i条路需要改变的量，且w[i]>=0

假设该路是大路，显然d[i]=c[i]-w[i];

假设该路是小路，显然d[i]=c[i]+w[i];

然后对于树环有限制条件：c[i]-w[i]<=c[j]+w[j]  (其中i为大路，j为小路)

变形成：w[i]+w[j]>=c[i]-c[j]。

于是KM里有不等式w[i]+w[j]>=P[i,j]。

然后由于最后KM的顶标之和等于最佳匹配的总权值，而对于该题而言，这个总权又是必须的。

于是两个问题等价了。

【CODE】

#include #include #include struct gtp{int x,y,w,op,next;}g[810];
int n,m,p,dis;
int w[405][405],fa[66],depth[66],lx[405],ly[405],link[405],ls[66];
bool cx[405],cy[405];

inline void swap(int &x,int &y){x=x^y; y=x^y; x=x^y;}
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++){
scanf("%d%d%d",&g[i].x,&g[i].y,&g[i].w);
g[i].next=ls[g[i].x];
ls[g[i].x]=i;
g[i].op=i+m;
}
for (int i=m+1;i<=2*m;i++){
g[i].x=g[i-m].y;
g[i].y=g[i-m].x;
g[i].w=g[i-m].w;
g[i].next=ls[g[i].x];
ls[g[i].x]=i;
g[i].op=i-m;
}
}

void buildtree(int p){
for (int t=ls[p];t;t=g[t].next)
if ((t fa[g[t].y]=t;
depth[g[t].y]=depth[p]+1;
buildtree(g[t].y);
}
}

void buildgraph(){
memset(w,0,sizeof(w));
int i,x,y,Fa;
for (i=n;i<=m;i++){
x=g[i].x; y=g[i].y;
while (y!=x){
if (depth[x]>depth[y]) swap(x,y);
Fa=fa[y];
if (Fa>=n) Fa=g[Fa].op;
w[Fa][i-n+1]=max(0,g[Fa].w-g[i].w);
y=g[fa[y]].x;
}
}
p=max(n-1,m-n+1);
}

bool find(int i){
cx[i]=true;
int q;
for (int j=1;j<=p;j++)
if (lx[i]+ly[j]==w[i][j] && !cy[j]){
cy[j]=true;
q=link[j];
link[j]=i;
if (!q || find(q)) return true;
link[j]=q;
}
else if (!cy[j]) dis=min(dis,lx[i]+ly[j]-w[i][j]);
return false;
}

void KM(){
int i,j;
for (i=1;i<=p;i++)
for (j=1;j<=p;j++)
if (w[i][j]>lx[i])
lx[i]=w[i][j];
for (i=1;i<=p;i++){
for (;;){
for (j=1;j<=p;j++) cx[j]=false;
for (j=1;j<=p;j++) cy[j]=false;
dis=0x7FFFFFFF;
if (find(i)) break;
for (j=1;j<=p;j++) if (cx[j]) lx[j]-=dis;
for (j=1;j<=p;j++) if (cy[j]) ly[j]+=dis;
}
}
}

void output(){
for (int i=1;i<=p;i++) g[i].w-=lx[i];
for (int i=1;i<=p;i++) g[i+n-1].w+=ly[i];
for (int i=1;i<=m;i++)
printf("%dn",g[i].w);
}

int main(){
input();
buildtree(1);
buildgraph();
KM();
output();
}