题目描述
题解&＃xff1a;
每条边至少经过一次&＃xff0c;说明经过下界为$1$。
然后套有源汇上下界最小费用可行流板子。
口胡一下。
此类问题的建图通式为&＃xff1a;
1.假设原来的边流量上下界为$[l,r]$&＃xff0c;那么在新图中建流量上界为$(r-l)$的边&＃xff1b;
就是必须流的先流完&＃xff0c;不一定的一会再算。
2.统计一下每个点流入的$l$之和$ind$以及流出的$l$之和$otd$&＃xff0c;设$d&＃61;ind-otd$&＃xff1b;
若$d>0$&＃xff0c;则建一条从新源点到该点的、容量为$d$的边&＃xff0c;表示减下界的时候多减了&＃xff0c;要加回来&＃xff1b;
若$d<0$&＃xff0c;则建一条从该点到新汇点的、容量为$-d$的边&＃xff0c;表示加多了&＃xff0c;要减回来。
3.旧汇点->旧源点&＃xff0c;容量为$inf$&＃xff0c;有借有还再借不难
然后求新图的最小费用最大流&＃xff0c;答案即为最小费用&＃43;所有边的费用*下界。
代码&＃xff1a;
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N &＃61; 350;
const int inf &＃61; 0x3f3f3f3f;
const ll Inf &＃61; 0x3f3f3f3f3f3f3f3fll;
template
inline void read(T&x)
{T f &＃61; 1,c &＃61; 0;char ch&＃61;getchar();while(ch<&＃39;0&＃39;||ch>&＃39;9&＃39;){if(ch&＃61;&＃61;&＃39;-&＃39;)f&＃61;-1;ch&＃61;getchar();}while(ch>&＃61;&＃39;0&＃39;&&ch<&＃61;&＃39;9&＃39;){c&＃61;c*10&＃43;ch-&＃39;0&＃39;;ch&＃61;getchar();}x &＃61; f*c;
}
int n,hed[N],cnt&＃61;-1,S,T,otd[N],ind[N],SS,TT;
struct EG
{int to,nxt;ll f,w;
}e[60*N];
void ae(int f,int t,ll fl,ll wl)
{e[&＃43;&＃43;cnt].to &＃61; t;e[cnt].nxt &＃61; hed[f];e[cnt].f &＃61; fl;e[cnt].w &＃61; wl;hed[f] &＃61; cnt;
}
void AE(int f,int t,ll fl,ll wl)
{ae(f,t,fl,wl);ae(t,f,0,-wl);
}
int pre[N],fa[N];
ll dis[N],fl[N],ans;
bool vis[N];
bool spfa()
{queue<int>q;memset(dis,0x3f,sizeof(dis));dis[SS]&＃61;0,fl[SS]&＃61;Inf,vis[SS]&＃61;1;q.push(SS);while(!q.empty()){int u &＃61; q.front();q.pop();for(int j&＃61;hed[u];~j;j&＃61;e[j].nxt){int to &＃61; e[j].to;if(e[j].f&&dis[to]>dis[u]&＃43;e[j].w){dis[to]&＃61;dis[u]&＃43;e[j].w;fl[to]&＃61;min(fl[u],e[j].f);fa[to]&＃61;u,pre[to]&＃61;j;if(!vis[to]){vis[to]&＃61;1;q.push(to);}}}vis[u]&＃61;0;}return dis[TT]!&＃61;Inf;
}
ll mcmf()
{ll ret &＃61; 0;while(spfa()){ret&＃43;&＃61;fl[TT]*dis[TT];int u &＃61; TT;while(u!&＃61;SS){e[pre[u]].f-&＃61;fl[TT];e[pre[u]^1].f&＃43;&＃61;fl[TT];u&＃61;fa[u];}}return ret;
}
int main()
{read(n);S&＃61;1,T&＃61;n&＃43;1;SS&＃61;n&＃43;2,TT&＃61;n&＃43;3;memset(hed,-1,sizeof(hed));for(int k,t,w,i&＃61;1;i<&＃61;n;i&＃43;&＃43;){read(k);while(k--){read(t),read(w);ind[t]&＃43;&＃43;,otd[i]&＃43;&＃43;;AE(i,t,inf,w);ans&＃43;&＃61;w;}if(i!&＃61;1)AE(i,T,inf,0);}for(int i&＃61;1;i<&＃61;n&＃43;1;i&＃43;&＃43;){int d &＃61; ind[i]-otd[i];if(d<0)AE(i,TT,-d,0);else AE(SS,i,d,0);}AE(T,S,inf,0);ans&＃43;&＃61;mcmf();printf("%lld\n",ans);return 0;
}
京公网安备 11010802041100号