题解 P4553 【80人环游世界】

简单上下界最小费用流。 模型很简单，将每个点拆成$a_i$和$a_i'$，然后进行以下连边: $s$向$a_i$连边，权值为$0$,下界为$0$,上界为$m$。 $a_i$向$a_i'$连边，权值为$0$,下界为$v_i$,上界为$v_i$。 若存在$i$向$j$的连边，则$a_i'$向$a_j$连边,权值为$w_{i,j}$,下界为$0$,上界为$m$。 $a_i'$向$t$连边,权值为$0$,下界为$0$,上界为$m$。 $t$向$t'$连边,权值为$0$,下界为$0$,上界$m$。 那么答案就是$s$向$t'$的最小费用最大流。因为涉及到上下界问题,所以开超级源和超级汇补流,答案变为超级源和超级汇之间地最大流。时间复杂度$O(maxflow(n,n+m))$。 代码: ```cpp #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #define Rep(i,a,b) for(register int i=(a),i##end=(b);i<=i##end;++i) #define Repe(i,a,b) for(register int i=(a),i##end=(b);i>=i##end;--i) #define For(i,a,b) for(i=(a),i<=(b);++i) #define Forward(i,a,b) for(i=(a),i>=(b);--i) #define Chkmin(a,b) a=a<b?a:b #define Chkmax(a,b) a=a>b?a:b #define pb push_back template<typename T>inline void read(T &x){ T s=0,f=1;char k=getchar(); while(!isdigit(k)&&k^'-')k=getchar(); if(!isdigit(k)){f=-1;k=getchar();} while(isdigit(k)){s=s*10+(k^48);k=getchar();} x=s*f; } inline void write(int a,char ed='\n') { static short s[13],tp; if(!a){putchar('0'),putchar(ed);return;} for(tp=0;a;a/=10)s[++tp]=a%10; for(;tp;putchar(s[tp--]^48)); putchar(ed); } using namespace std; const int MAXN=411+7; static int n,m,e=1,head[MAXN]; static struct edge { int v,nxt,w,f; }p[MAXN*MAXN]; inline void add(int u,int v,int w,int f,int laz=1) { p[++e]=(edge){v,head[u],w,f};head[u]=e; if(laz)add(v,u,-w,0,0); } static int s,t,ss,tt,kt; const int inf=0x3f3f3f3f; inline void init() { read(n);read(m);s=2*n+1;t=s+1;kt=t+1,ss=kt+1;tt=ss+1; static int x; Rep(i,1,n)read(x),add(ss,i+n,0,x) ,add(i,tt,0,x),add(s,i,0,m),add(i+n,t,0,m); add(t,kt,0,m); add(kt,s,0,inf); Rep(i,1,n)Rep(j,i+1,n) { read(x); if(~x)add(n+i,j,x,inf); } } static int cost; static deque<int>G; static int dis[MAXN],vis[MAXN],cur[MAXN]; inline bool spfa(int s,int t) { memset(dis,0x3f,sizeof dis); dis[s]=0;G.push_back(s); static int u; while(!G.empty()) { u=G.front();G.pop_front();vis[u]=false; for(register int v=head[u];v;v=p[v].nxt) if(p[v].f&&dis[p[v].v]>dis[u]+p[v].w) { dis[p[v].v]=dis[u]+p[v].w; if(!vis[p[v].v]) { vis[p[v].v]=true; if(G.empty()||dis[p[v].v]<dis[G.front()]) G.push_front(p[v].v); else G.push_back(p[v].v); } } } return dis[t]^dis[0]; } int dfs(int u,int t,int flow=inf) { if(u==t||!flow)return flow; vis[u]=true; int sum=0,f; for(register int&v=cur[u];flow&&v;v=p[v].nxt) if(!vis[p[v].v]&&p[v].f&&dis[p[v].v]==dis[u]+p[v].w) { f=dfs(p[v].v,t,min(flow,p[v].f)); p[v].f-=f;p[v^1].f+=f;sum+=f;flow-=f; cost+=p[v].w*f; } vis[u]=false; return sum; } inline void Dinic(int s,int t) {while(spfa(s,t))memcpy(cur,head,sizeof head),dfs(s,t);} inline void solve() { Dinic(ss,tt); printf("%d\n",cost); } inline void file() { #ifndef ONLINE_JUDGE freopen("water.in","r",stdin); freopen("water.out","w",stdout); #endif } int main() { file(); init(); solve(); cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl; return 0; } ```