题解 P3171 【[CQOI2015]网络吞吐量】
前言:
本来自己曾想到与这道题一模一样的模型的，我本来还准备自己出道这样的题的，结果被自己省的省选先出了，那就只能写篇题解了。。。
思路：
通过分析，我们可以得出，这道题实质所求的是：
在第i个点只能选
设
若我们要走
然后现在只剩下满足条件的边后，思路也很明显了，很显然这是一个最大流的问题，但是唯一讨厌的就是改题是对经过点的容量进行了限制，而不是对边。
那怎么办呢？
做过一些最大流的同学也都知道，现在当然就该拆点了。
拆完点，然后跑最大流就好了。
做法：
先跑最短路，留下在最短路中的边。
将
从第
对于每条在最短路中的
从源点
最后跑最大流即可。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#define inf 0x7fffffffff/2
#define eps 1e-6
#define N 2010
#define M 100010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
char ch=getchar();
ll s=0,w=1;
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
return s*w;
}
ll dist[N];//这道题最坑的就是没开long long 0分,rip for 2015年参加省选没开long long的学长们
struct edge
{
int next,to;
ll fl;
}e[M<<1];
int cnt=1,head[N];
int n,m;
int vis[N];
ll c[N];
int s,t;
int depth[N];
queue<int>Q;
vector<int>to[N];
vector<ll>v[N];
inline void add_edge(int from,int to,ll fl)
{
e[++cnt].to=to;
e[cnt].next=head[from];
e[cnt].fl=fl;
head[from]=cnt;
}//建边
inline int bfs()
{
while(!Q.empty())Q.pop();memset(depth,0,sizeof(depth));
Q.push(s);depth[s]=1;
while(!Q.empty())
{
int x=Q.front();Q.pop();
for(register int i=head[x];i;i=e[i].next)
{
if(!depth[e[i].to]&&e[i].fl>0)
{
depth[e[i].to]=depth[x]+1;
Q.push(e[i].to);
}
}
}
return depth[t];
}
ll dfs(int now,ll flow)
{
if(now==t)return flow;
ll ret=0;
for(register int i=head[now];i;i=e[i].next)
{
if(ret==flow)return ret;
if(depth[e[i].to]==depth[now]+1&&e[i].fl>0)
{
ll fl=dfs(e[i].to,min(flow-ret,e[i].fl));
if(fl>0)
{
ret+=fl;
e[i].fl-=fl;
e[i^1].fl+=fl;
}
}
}
return ret;
}
inline ll Dinic()
{
ll sum=0;
while(bfs())
{
ll x=1;while(x){x=dfs(s,inf);sum+=x;}
}
return sum;
}//最大流
inline void spfa()
{
for(register int i=2;i<=n;i++)dist[i]=inf;
while(!Q.empty())Q.pop();
Q.push(1);vis[1]=1;
while(!Q.empty())
{
int x=Q.front();Q.pop();vis[x]=0;
for(register int i=0;i<to[x].size();i++)
{
int go=to[x][i];
ll val=v[x][i];
if(dist[x]+val<dist[go])
{
dist[go]=dist[x]+val;
if(!vis[go])
{
vis[go]=1;
Q.push(go);
}
}
}
}
}//最短路，Dijkstra过不了·
int main()
{
n=read(),m=read();
t=n*2+1;
for(register int i=1;i<=m;i++)
{
int x=read(),y=read();
ll val=read();
to[x].push_back(y);v[x].push_back(val);
to[y].push_back(x);v[y].push_back(val);
}
spfa();
for(register int i=1;i<=n;i++)c[i]=read();
add_edge(s,1,inf);add_edge(1,s,0);
add_edge(2*n,t,inf);add_edge(t,2*n,0);
for(register int i=1;i<=n;i++)
{
if(i!=1&&i!=n){add_edge(i,i+n,c[i]);add_edge(i+n,i,0);}
else {add_edge(i,i+n,inf),add_edge(i+n,i,0);}
}//通过拆点对每个点经过的流量进行限制
for(register int i=1;i<=n;i++)
{
for(register int j=0;j<to[i].size();j++)
{
int go=to[i][j];
ll val=v[i][j];
if(dist[go]==dist[i]+val)//在最短路中
{
add_edge(i+n,go,inf);add_edge(go,i+n,0);
}
}
}//对在最短路中的边建边
printf("%lld\n",Dinic());
return 0;
}
后记：
这道题与网络流24题中的最长不下降序列问题类似，都是对DP方案数的讨论（最短路我认为也是一种DP），做完这道题没做那道题的经验可以去A一下（双倍经验）