BZOJ 1937 Mst最小生成树

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

Description

Input

第一行为N、M,其中 表示顶点的数目, 表示边的数目。顶点的编号为1、2、3、……、N-1、N。接下来的M行,每行三个整数Ui,Vi,Wi,表示顶点Ui与Vi之间有一条边,其权值为Wi。所有的边在输入中会且仅会出现一次。再接着N-1行,每行两个整数Xi、Yi,表示顶点Xi与Yi之间的边是T的一条边。

Output

输出最小权值

Sample Input

6 9
1 2 2
1 3 2
2 3 3
3 4 3
1 5 1
2 6 3
4 5 4
4 6 7
5 6 6
1 3
2 3
3 4
4 5
4 6

Sample Output

8

【样例说明】 边(4,6)的权由7修改为3,代价为4
边(1,2)的权由2修改为3,代价为1
边(1,5)的权由1修改为4,代价为3
所以总代价为4+1+3=8
修改方案不唯一。

HINT

1<=n<=50,1<=m<=800,1<=wi<=1000
n-->点数..m-->边数..wi--->边权


题解

这道题的题意是要求修改一些边的权值使得给出的树成为这个图的最小生成树,求最小代价。
注意到我们只可能增大非树边,减小树边。

那么对于一个树边ii和一个可能影响到最小生成树的非树边jj,我们一定要满足如下条件:
widiwj+djwi−di≤wj+dj
移项,即
wiwjdi+djwi−wj≤di+dj
其中d表示我们对于边的改动值(一定非负)
这样就可以转化成二分图最小顶标和来做。
我们把边看成点,两原边边权之差作为新点之间的边权,跑一边KM或者最小费用最大流就可以了。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=1005,M=2e5+5,INF=1e9;
int get_num(){
	int num = 0;
	char c;
	bool flag = false;
	while((c = getchar()) == ' ' || c == '\r' || c == '\n');
	if(c == '-')
		flag = true;
	else num = c - '0';
	while(isdigit(c = getchar()))
		num = num * 10 + c - '0';
	return (flag ? -1 : 1) * num;
}
int n,m,s,t,g[55][55],u,v,id[55][55],num;
struct data{int u,v,w;}a[M];

int q[N],p;
struct Graph{
    struct edge{int v,ne;}e[M];
    int cnt,h[N];
    inline void ins(int u,int v){
        cnt++;
        e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;
        cnt++;
        e[cnt].v=u;e[cnt].ne=h[v];h[v]=cnt;
    }
    bool dfs(int u,int fa,int tar){
        if(u==tar) return true;
        for(int i=h[u];i;i=e[i].ne)
            if(e[i].v!=fa){
                q[++p]=id[u][e[i].v];
                if(dfs(e[i].v,u,tar)) return true;
                p--;
            }
        return false;
    }
}G;

struct Edge{
    int v,ne,w,c,f;
    Edge(){}
    Edge(int v,int w,int c,int f):v(v),w(w),c(c),f(f){}
}e[M];
int cnt,h[N];
inline void ins(int u,int v,int w,int c){
    cnt++;
    e[cnt]=Edge(v,w,c,0);e[cnt].ne=h[u];h[u]=cnt;
    cnt++;
    e[cnt]=Edge(u,-w,0,0);e[cnt].ne=h[v];h[v]=cnt;
}

void build(){
    s=0;t=m+1;
    for(int i=1;i<n;i++)
		ins(s,i,0,1);
    for(int i=n;i<=m;i++)
		ins(i,t,0,1);
    for(int i=n;i<=m;i++){
        p=0;
        G.dfs(a[i].u,0,a[i].v);
        for(int j=1;j<=p;j++) ins(q[j],i,a[q[j]].w-a[i].w,1);
    }
}

int d[N],head,tail,inq[N],pre[N],pos[N];
inline void lop(int &x){if(x==N)x=1;}
bool spfa(){
    //memset(d,127,sizeof(d));
    for(int i=s;i<=t;i++) d[i]=-INF,inq[i]=0;
    //memset(inq,0,sizeof(inq));
    head=tail=1;
    d[s]=0;inq[s]=1;q[tail++]=s;
    pre[t]=-1;
    while(head!=tail){
        int u=q[head++];inq[u]=0;lop(head);
        for(int i=h[u];i;i=e[i].ne){
            int v=e[i].v,w=e[i].w;
            if(d[v]<d[u]+w&&e[i].c>e[i].f){
                d[v]=d[u]+w;
                pre[v]=u;pos[v]=i;
                if(!inq[v])q[tail++]=v,inq[v]=1,lop(tail); 
            }
        }
    }
    return pre[t]!=-1;
}
int mcmf(){
    int flow=0,cost=0;
    while(spfa()){
        int f=INF;
        for(int i=t;i!=s;i=pre[i]) f=min(f,e[pos[i]].c-e[pos[i]].f);
        flow+=f; 
        if(d[t]<0) break;
        cost+=d[t]*f;
        for(int i=t;i!=s;i=pre[i]){
            e[pos[i]].f+=f;
            e[((pos[i]-1)^1)+1].f-=f;
        }
    }
    return cost;
}

int main(){
    n=get_num();m=get_num(); 
    for(int i=1;i<=m;i++){
		u=get_num();
		v=get_num();
		g[u][v]=g[v][u]=get_num();
	}
    for(int i=1;i<n;i++){
		u=get_num();
		v=get_num();
		id[u][v]=id[v][u]=++num;
		a[num]=(data){u,v,g[u][v]};
		G.ins(u,v);
	}
    for(int i = 1;i <= n;i++)
        for(int j = i+1;j <= n;j++) 
            if(g[i][j]&&!id[i][j]){
				id[i][j] = id[j][i] = ++num;
				a[num]=(data){i,j,g[i][j]};
			}

    build();
    printf("%d\n",mcmf());
    return 0;
}
Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00