傳送門
題意：
給一張無向圖和一棵生成樹，改變一些邊的權值使生成樹為最小生成樹，代價為改變權值和的絕對值，求最小代價
?
線性規劃的形式：
$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()); }
?
