题目描述
传送门
题解
这题我的方法好蠢啊
令xi表示第i条边增加了几次，yi表示第i条边减少了几次，那么目标函数就是最小化∑Ai∗xi+Bi∗yi
然后对于每一条非树边，它的两个端点对应的树链上的每一条边都应该小于这条非树边，也就是说，xi−yi+wi≤xj−yj+wj，因为wi和wj的大小不定，但是Ai和Bi一定是正数，所以要将矩阵对偶来满足初始可行解。也就是化成xj−xi−yj+yi≤wi−wj的形式
然后用单纯形解就行了
但是实际上非树边只会增大，树边只会减小，所以一条边设一个未知量就行了，gg
感觉最坏情况下是可以卡成m2的啊，但是这题没有卡
代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const double eps=1e-9;
const double inf=1e18;
int N,M,U[1005],V[1005],W[1005],A[1005],B[1005],FF[1005];
int tot,point[305],nxt[2005],v[2005],num[2005],h[205],father[305],last[305];
int n,m;
double a[4005][4005],b[4005],c[4005],ans;
void add(int x,int y,int id)
{
++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; num[tot]=id;
}
void dfs(int x,int fa)
{
h[x]=h[fa]+1;father[x]=fa;
for (int i=point[x];i;i=nxt[i])
if (v[i]!=fa)
{
last[v[i]]=num[i];
dfs(v[i],x);
}
}
void build(int x,int y,int id)
{
int jd;
// xj-xi-yj+yi<=wi-wj
if (h[x]<h[y]) swap(x,y);
while (h[x]>h[y])
{
jd=last[x];
++n;
a[jd][n]=-1.0;a[id][n]=1.0;a[jd+M][n]=1.0;a[id+M][n]=-1.0;
c[n]=W[jd]-W[id]+0.0;
x=father[x];
}
while (x!=y)
{
jd=last[x];
++n;
a[jd][n]=-1.0;a[id][n]=1.0;a[jd+M][n]=1.0;a[id+M][n]=-1.0;
c[n]=W[jd]-W[id]+0.0;
x=father[x];
jd=last[y];
++n;
a[jd][n]=-1.0;a[id][n]=1.0;a[jd+M][n]=1.0;a[id+M][n]=-1.0;
c[n]=W[jd]-W[id]+0.0;
y=father[y];
}
}
void pivot(int l,int e)
{
b[l]/=a[l][e];
for (int i=1;i<=n;++i)
if (i!=e) a[l][i]/=a[l][e];
a[l][e]=1.0/a[l][e];
for (int i=1;i<=m;++i)
if (i!=l&&fabs(a[i][e])>eps)
{
b[i]-=a[i][e]*b[l];
for (int j=1;j<=n;++j)
if (j!=e)
a[i][j]-=a[i][e]*a[l][j];
a[i][e]=-a[i][e]*a[l][e];
}
ans+=b[l]*c[e];
for (int i=1;i<=n;++i)
if (i!=e)
c[i]-=c[e]*a[l][i];
c[e]=-c[e]*a[l][e];
}
void simplex()
{
while (1)
{
int e;
for (e=1;e<=n;++e)
if (c[e]>eps) break;
if (e==n+1) break;
double Min=inf,t;int l;
for (int i=1;i<=m;++i)
if (a[i][e]>eps&&(t=b[i]/a[i][e])<Min)
{
Min=t;
l=i;
}
pivot(l,e);
}
}
int main()
{
scanf("%d%d",&N,&M);
for (int i=1;i<=M;++i)
{
scanf("%d%d%d%d%d%d",&U[i],&V[i],&W[i],&FF[i],&A[i],&B[i]);
if (FF[i]) add(U[i],V[i],i),add(V[i],U[i],i);
}
dfs(1,0);
m=M*2;
for (int i=1;i<=M;++i)
b[i]=A[i]+0.0,b[i+M]=B[i]+0.0;
for (int i=1;i<=M;++i)
if (!FF[i]) build(U[i],V[i],i);
simplex();
PRintf("%.0lf\n",ans);
}
