.gif)
NOI 2008 志愿者招募 題解 (神奇費用流)
思路很清奇的網絡流題
這種第i天需要至少\(a_i\)人的限制，按常規思路容易想到在i號點和i+1號點之間連一條容量為\(a_i\)的邊，并強制流滿。但是如果雇傭了一個人，他只能從\(s_i天工作到t_i\)天，我們無法控制他只流這個區間內的邊，所以需要換一種思路。
考慮如下建圖。對于第i天的限制，我們從第i個點到第i+1個點連一條邊，費用為0，先不管它的容量是多少，反正這條邊代表第i天的限制。然后對于第i類人，從第\(s_i\)個點到第\(t_i+1\)個點連容量為inf，費用為\(c_i\)的邊，這條邊的最終流量就代表招募的這種人的個數。然后從源點到第1個點連容量為inf費用為0的邊，從第n+1個點到匯點也連一樣的邊。其實這個圖跑最小費用最大流的最終費用就是答案(第一類邊的容量接下來說明)，考慮證明。
令這個圖的最大流量為tot。由于這個圖是一個dag，根據網絡流的性質，在取最小費用最大流時，對任意i，第\(i(1\le i \le n)\)個點到第\(i+1\)個點的所有邊(包括直接相連的邊以及跨過i和i+1中間這個空檔的志愿者邊)的總流量是tot。我們希望對于任意i，跨過i和i+1之間的空檔的志愿者邊的流量總和\(\ge a_i\)，這等價于i和i+1之間直接相連的那條邊的流量\(\le tot-a_i\)。如果我們令每條\(i\to i+1\)的邊的容量為\(inf-a_i\)(注意這題中提到的inf都不是無窮，而是一個很大的數比如1e16)，其實這個圖的最大流量就是inf(這個待會證明)，也就是tot=inf，且此時顯然每條\(i\to i+1\)的邊流量都不超過\(tot-a_i\)，所以在這個情況下求出的最小費用最大流的費用就是答案。
然后來證明這個圖的最大流是inf。首先由于源點到1號點的容量就是inf，所以最大流不會超過inf。由于題目保證有解，那么假設我們隨意取出一組解(不需要費用最小)，并按照這個解先分配好每條志愿者邊的流量。然后強制這個圖的總流量是inf，然后從左往右推，該由志愿者邊分流的時候就分流，其余的直接沿著\(i\to i+1\)的邊往前流，發現永遠不會發生邊容量不夠的情況，所以最大流\(\ge inf\)。綜上，最大流量就是inf。
點擊查看代碼
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <LL,LL>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nEXECUTION TERMINATED";
#endif
exit(0);
}
using namespace std;
struct edge
{
LL to,flow,cost,rev;
edge(LL a,LL b,LL c,LL d):to(a),flow(b),cost(c),rev(d){}
};
namespace minCostFlow
{
vector <edge> g[10010];
LL n,dist[10010],cur[10010];
bool inq[10010],vis[10010];
queue <LL> q;
void add_edge(LL x,LL y,LL flow,LL cost)
{
g[x].pb(edge(y,flow,cost,(LL)g[y].size()));
g[y].pb(edge(x,0,-cost,(LL)g[x].size()-1));
}
bool relax(LL to,LL fr,LL e)
{
if(dist[to]>dist[fr]+e)
{
dist[to]=dist[fr]+e;
return true;
}
return false;
}
bool spfa(LL s,LL t)
{
rep(i,n+3) dist[i]=1e18;
dist[s]=0;inq[s]=true;q.push(s);
while(!q.empty())
{
LL p=q.front();q.pop();inq[p]=false;
rep(i,g[p].size()) if(g[p][i].flow>0)
{
if(relax(g[p][i].to,p,g[p][i].cost)&& !inq[g[p][i].to])
{
inq[g[p][i].to]=true;
q.push(g[p][i].to);
}
}
}
return dist[t]<1e18;
}
pii dfs(LL pos,LL t,LL fl)
{
if(pos==t) return mpr(fl,0);
vis[pos]=true;
for(LL i=cur[pos];i<g[pos].size();++i,++cur[pos]) if(!vis[g[pos][i].to]&&g[pos][i].flow>0&&dist[g[pos][i].to]==dist[pos]+g[pos][i].cost)
{
pii res=dfs(g[pos][i].to,t,min(fl,g[pos][i].flow));
if(res.fi>0)
{
res.se+=g[pos][i].cost*res.fi;
g[pos][i].flow-=res.fi;g[g[pos][i].to][g[pos][i].rev].flow+=res.fi;
vis[pos]=false;
return res;
}
}
vis[pos]=false;
return mpr(0,0);
}
pii mcmf(LL s,LL t)
{
pii ret=mpr(0,0);
while(spfa(s,t))
{
rep(i,n+3) cur[i]=0;
while(true)
{
pii val=dfs(s,t,1e18);
if(val.fi==0) break;
ret.fi+=val.fi;ret.se+=val.se;
}
}
return ret;
}
}
LL n,m,a[1010];
int main()
{
fileio();
cin>>n>>m;
repn(i,n) scanf("%lld",&a[i]);
LL ss=n+2,tt=n+3,inf=1e16;
minCostFlow::add_edge(ss,1,inf,0);minCostFlow::add_edge(n+1,tt,inf,0);
repn(i,n) minCostFlow::add_edge(i,i+1,inf-a[i],0);
rep(i,m)
{
LL x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
minCostFlow::add_edge(x,y+1,inf,z);
}
minCostFlow::n=n+3;
cout<<minCostFlow::mcmf(ss,tt).se<<endl;
termin();
}
浙公網安備 33010602011771號