[BZOJ1937][SHOI2004]Mst最小生成树(KM算法,最大费用流)

1937: [Shoi2004]Mst 最小生成树

Time Limit: 3 Sec Memory Limit: 64 MB
Submit: 802 Solved: 344
[Submit][Status][Discuss]

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--->边权

Source

[Submit][Status][Discuss]

注意到我们只可能增大树边，减小非树边，那么设每条边的改动幅度为$|d[i]|$，那么对于一条树边i和非树边j，必有$w[i]-d[i] \leqslant w[j]+d[j]$，即$w[i]-w[j] \leqslant d[i]+d[j]$。于是我们把边看作点，按是否为树边将所有边分成二分图，树边i与非树边j的边设为w[i]-w[j]。可以发现d[i]实际上就是KM算法中的顶标。所以求一次KM算法并将所有匹配相加就是答案，因为不在匹配里的d[i]直接作为0即可。

重新复习一下KM算法。先将X部分的d[x]设为$max\{w[x][y]\}$，Y部分的d[y]设为0，然后求m次增广（直到有完备匹配）。每次增广如果失败，则设$mn=min\{a[i]+b[j]-w[i][j]\}$，将所有交错树上的d[x]+=mn,d[y]-=mn。

理论依据：若由二分图中所有满足A[i]+B[j]=w[i][j]的边<i,j>构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。所以这是一个不断修改顶标并在相等子图上做完备匹配的过程。（任意i,j保证$d[i]+d[j] \geqslant w[i][j]$）。

定理：每次增广顶标和必然变小，最后一定是满足$d[i]+d[j] \geqslant w[i][j]$的最小可能。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define mem(a,k) memset(a,k,sizeof(a))

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 using namespace std;

 const int N=,inf=0x3f3f3f3f;

 int n,m,u,v,ww,x,y,ans;

 int mp[][],w[][],lk[],lx[],ly[],vx[],vy[],s[],dep[],fa[][];

 bool chk[][];

 struct E{ int u,v,w;}e[];

 void dfs(int x,int f){

     fa[x][]=f; dep[x]=dep[f]+;

     rep(i,,) fa[x][i]=fa[fa[x][i-]][i-];

     rep(i,,n) if (i!=f && chk[x][i]) dfs(i,x);

 }

 int LCA(int x,int y){

     if (dep[x]<dep[y]) swap(x,y);

     int t=dep[x]-dep[y];

     for (int i=; ~i; i--) if (t&(<<i)) x=fa[x][i];

     if (x==y) return x;

     for (int i=; ~i; i--) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];

     return fa[x][];

 }

 bool find(int x){

     vx[x]=;

     rep(y,,m) if (!vy[y]){

         int t=lx[x]+ly[y]-w[x][y];

         if (t==){

             vy[y]=; if (lk[y]==- || find(lk[y])) { lk[y]=x; return ; }

         }else s[y]=min(s[y],t);

     }

     return ;

 }

 void KM(){

     mem(lk,-); mem(lx,-inf); mem(ly,);

     rep(i,,m) rep(j,,m) lx[i]=max(lx[i],w[i][j]);

     rep(x,,m){

         rep(i,,m) s[i]=inf;

         while (){

             mem(vx,); mem(vy,);

             if (find(x)) break;

             int d=inf;

             rep(i,,m) if (!vy[i]) d=min(d,s[i]);

             rep(i,,m) if (vx[i]) lx[i]-=d;

             rep(i,,m) if (vy[i]) ly[i]+=d; else s[i]-=d;

         }

     }

     rep(i,,m) if (lk[i]!=-) ans+=w[lk[i]][i];

 }

 int main(){

     scanf("%d%d",&n,&m);

     rep(i,,m) scanf("%d%d%d",&u,&v,&ww),e[i]=(E){u,v,ww},mp[u][v]=mp[v][u]=i;

     rep(i,,n) scanf("%d%d",&x,&y),chk[x][y]=chk[y][x]=;

     dfs(,);

     rep(i,,m){

         int x=e[i].u,y=e[i].v,lca=LCA(x,y);

         if (!chk[x][y]){

             while (x!=lca) w[mp[x][fa[x][]]][i]=e[mp[x][fa[x][]]].w-e[i].w,x=fa[x][];

             while (y!=lca) w[mp[y][fa[y][]]][i]=e[mp[y][fa[y][]]].w-e[i].w,y=fa[y][];

         }

     }

     KM(); printf("%d\n",ans);

     return ;

 }

好久没写最大费用最大流了发现自己完全不会写，调了整整一上午。需要注意：dis[]初始要赋为-inf，bfs()返回真的条件是dis[T]>0，其余不变。因为边里会有负值。

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define rep(i,l,r) for (int i=l; i<=r; i++)

 #define For(i,x) for (int i=h[x],k; i; i=nxt[i])

 typedef long long ll;

 using namespace std;

 const int N=,inf=0x3f3f3f3f;

 int n,m,u,v,w,x,y,S,T,mn,cnt=,ans;

 int to[N],f[N],c[N],nxt[N],h[],pre[],dis[],q[N];

 int mp[][],dep[],fa[][];

 bool inq[N],chk[][];

 struct E{ int u,v,w;}e[];

 void add(int u,int v,int w,int co){

     to[++cnt]=v; f[cnt]=w; c[cnt]=co; nxt[cnt]=h[u]; h[u]=cnt;

     to[++cnt]=u; f[cnt]=; c[cnt]=-co; nxt[cnt]=h[v]; h[v]=cnt;

 }

 bool spfa(){

     rep(i,,T) dis[i]=-inf,pre[i]=-,inq[i]=;

     dis[S]=; inq[S]=; q[]=S;

     for (int st=,ed=; st!=ed; ){

         int x=q[++st]; inq[x]=;

         For(i,x) if (f[i] && dis[k=to[i]]<dis[x]+c[i]){

             dis[k]=dis[x]+c[i]; pre[k]=i;

             if (!inq[k]) inq[k]=,q[++ed]=k;

         }

     }

     return dis[T]>;

 }

 void mcmf(){

     for (ans=; spfa(); ans+=dis[T]*mn){

         mn=inf;

         for (int i=pre[T]; ~i; i=pre[to[i^]]) mn=min(mn,f[i]);

         for (int i=pre[T]; ~i; i=pre[to[i^]]) f[i]-=mn,f[i^]+=mn;

     }

 }

 void dfs(int x,int f){

     fa[x][]=f; dep[x]=dep[f]+;

     rep(i,,) fa[x][i]=fa[fa[x][i-]][i-];

     rep(i,,n) if (i!=f && chk[x][i]) dfs(i,x);

 }

 int LCA(int x,int y){

     if (dep[x]<dep[y]) swap(x,y);

     int t=dep[x]-dep[y];

     for (int i=; ~i; i--) if (t&(<<i)) x=fa[x][i];

     if (x==y) return x;

     for (int i=; ~i; i--) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];

     return fa[x][];

 }

 int main(){

     freopen("bzoj1937.in","r",stdin);

     freopen("bzoj1937.out","w",stdout);

     scanf("%d%d",&n,&m);

     rep(i,,m) scanf("%d%d%d",&u,&v,&w),e[i]=(E){u,v,w},mp[u][v]=mp[v][u]=i;

     rep(i,,n) scanf("%d%d",&x,&y),chk[x][y]=chk[y][x]=;

     dfs(,); S=m+; T=m+;

     rep(i,,m){

         int x=e[i].u,y=e[i].v;

         if (chk[x][y]) add(S,i,,);

         else{

             add(i,T,,); int lca=LCA(x,y);

             while (x!=lca) add(mp[x][fa[x][]],i,,e[mp[x][fa[x][]]].w-e[i].w),x=fa[x][];

             while (y!=lca) add(mp[y][fa[y][]],i,,e[mp[y][fa[y][]]].w-e[i].w),y=fa[y][];

         }

     }

     mcmf(); printf("%d\n",ans);

     return ;

 }

巴特西

[BZOJ1937][SHOI2004]Mst最小生成树(KM算法,最大费用流)

1937: [Shoi2004]Mst 最小生成树

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最新文章

热门文章