题目链接：bzoj1937 题目大意：
题解： KM/费用流 看不懂题解的我%了发男神 首先显然的，对于T上的边只进行减小操作，非T上的边只进行增加操作。（当然也可以不改变） 因为已经要求了一棵最小生成树T，即让非T上的边都不选。那么它不选的理由是什么呢？ 假设这条非T的边编号为j，连接x->y，如果它不选的话，那么它的边权w[j]一定大于所以x->y在T中的路径上的边的边权，才会不选它。不然，因为图的连通性还是得到保证的，就会去掉一条边权比j大的边而选择j。 设delta[i]表示i这条边修改的量。于是就有w[i]-delta[i]<=w[j]+delta[j]，移项后得w[i]-w[j]<=delta[i]+delta[j]，然后不就可以把delta看成KM的顶标吗，而i->j的边权就是w[i]-w[j]啊。
吐槽.. 我想练练KM而找的这题。。结果KM打得一塌糊涂qwq 而奥爷爷在我问了他的快一天后来做这题，然后在我之前A掉了这题qwq 直接上费用流32ms，，而我调了一年的KM八百多ms。。。 心好累啊
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define N 60 #define M 1000 const int inf=0xfffffff; struct node { int x,y,c,next,id; }T[M*2]; int d[M][M]; int len,first[M]; struct edge { int x,y,c;bool bk; }a[M]; int id[N][N],tim,n,m; int bf[M],slack[M],lx[M],ly[M]; int mymin(int x,int y){return (x<y)?x:y;} int mymax(int x,int y){return (x>y)?x:y;} void ins(int x,int y,int c,int p) { len++;T[len].x=x;T[len].y=y;T[len].c=c; T[len].id=p;T[len].next=first[x];first[x]=len; } int visx[M],visy[M]; int dep[N],fa[N][10],upe[N]; bool vis[N]; void dfs(int x) { vis[x]=true; for (int i=first[x];i!=-1;i=T[i].next) { int y=T[i].y; if (!vis[y]) { fa[y][0]=x; dep[y]=dep[x]+1; upe[y]=T[i].id; dfs(y); } } } int lca(int x,int y) { if (dep[x]<dep[y]) {int t=x;x=y;y=t;} for (int i=8;i>=0;i--) if (dep[x]-dep[y]>=(1<<i)) x=fa[x][i]; if (x==y) return x; for (int i=8;i>=0;i--) if (dep[x]>(1<<i) && fa[x][i]!=fa[y][i]) { x=fa[x][i]; y=fa[y][i]; } return fa[x][0]; } void bt(int x,int p,int k) { while (x!=p) { d[upe[x]][k]=mymax(0,a[upe[x]].c-a[k].c); x=fa[x][0]; } } bool ffind(int x) { visx[x]=tim; for (int y=1;y<=m;y++) if (visy[y]!=tim) { if (lx[x]+ly[y]==d[x][y]) { visy[y]=tim; if (bf[y]==-1 || ffind(bf[y])) { bf[y]=x; return true; } }else slack[y]=mymin(slack[y],lx[x]+ly[y]-d[x][y]); } return false; } void KM() { tim=0;int i,j; for (i=1;i<=m;i++) lx[i]=-inf,visx[i]=ly[i]=visy[i]=0,bf[i]=-1; for (i=1;i<=m;i++) for (j=1;j<=m;j++) lx[i]=mymax(lx[i],d[i][j]); for (i=1;i<=m;i++) { for (j=1;j<=m;j++) slack[j]=inf; while (1) { tim++; if (ffind(i)) break; int delta=inf; for (j=1;j<=m;j++) if (visy[j]!=tim) delta=mymin(delta,slack[j]); for (j=1;j<=m;j++) { if (visx[j]==tim) lx[j]-=delta; if (visy[j]==tim) ly[j]+=delta; else slack[j]-=delta; } } } } int main() { //freopen("a.in","r",stdin); //freopen("a.out","w",stdout); int i,j,x,y,c; scanf("%d%d",&n,&m); len=0;memset(first,-1,sizeof(first)); for (i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&c); if (x>y) {int t=x;x=y;y=t;} a[i].x=x;a[i].y=y;a[i].c=c; id[x][y]=i;a[i].bk=false; } for (i=1;i<n;i++) { scanf("%d%d",&x,&y); if (x>y) {int t=x;x=y;y=t;} ins(x,y,a[id[x][y]].c,id[x][y]); ins(y,x,a[id[x][y]].c,id[x][y]); a[id[x][y]].bk=true; vis[i]=false; } vis[n]=false;dep[1]=1;dfs(1); for (j=1;j<=8;j++) for (i=2;i<=n;i++) fa[i][j]=fa[fa[i][j-1]][j-1]; for (i=1;i<=m;i++) if (!a[i].bk) { int lc=lca(a[i].x,a[i].y); bt(a[i].x,lc,i); bt(a[i].y,lc,i); } KM(); int ans=0; for (i=1;i<=m;i++) if (a[i].bk) ans+=lx[i];else ans+=ly[i]; printf("%d\n",ans); return 0; }转载于:https://www.cnblogs.com/Euryale-Rose/p/6527792.html
