首页 > 代码库 > BZOJ 1937: [Shoi2004]Mst 最小生成树 [二分图最大权匹配]

BZOJ 1937: [Shoi2004]Mst 最小生成树 [二分图最大权匹配]

传送门

题意:

给一张无向图和一棵生成树,改变一些边的权值使生成树为最小生成树,代价为改变权值和的绝对值,求最小代价


 

线性规划的形式:

$Min\quad \sum\limits_{i=1}^{m} \delta_i$

$Sat\quad $非树边边权$\ge$生成树上路径任何一条边的边权

$i$非树边$j$树边

$w_i+\delta_i \ge w_j-\delta_j$

然后可以转化成二分图最小顶标和来求解

 

这里需要求二分图最大权非完美匹配,我的做法是遇到$d[t] < 0$就退出,反正这道题过了

 

然后很高兴的$1A$了就去看金刚狼3了好感动 现在补题解...

 

#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;inline int read(){    char c=getchar();int x=0,f=1;    while(c<0||c>9){if(c==-)f=-1;c=getchar();}    while(c>=0&&c<=9){x=x*10+c-0;c=getchar();}    return x*f;}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){//printf("ins %d %d    %d    %d\n",u,v,w,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);        //printf("now %d\n",i);        //for(int j=1;j<=p;j++) printf("%d ",q[j]);puts("");        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;//printf("%d %d %d\n",f,d[t],cost);        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(){    freopen("in","r",stdin);    n=read();m=read();     for(int i=1;i<=m;i++)         u=read(),v=read(),g[u][v]=g[v][u]=read();    for(int i=1;i<n;i++)         u=read(),v=read(),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]};                //printf("lo %d %d %d\n",i,j,num);    build();    printf("%d\n",mcmf());}

 

BZOJ 1937: [Shoi2004]Mst 最小生成树 [二分图最大权匹配]