题解 P3171 【[CQOI2015]网络吞吐量】 非完美解法
wjyyy
2018-07-07 17:08:39
来发一篇非完美解法的题解;[我的博客](http://www.wjyyy.top/771.html)
# 非完美解法:
看到这个题,用网络流来**限流**当然是第一想法。于是先spfa求最短路,接着枚举每个点是否在最短路上。判断方法:从起点/终点出发各跑一遍最短路,记录dis[0]和dis[1],最后枚举每条边是否满足$dis[0][u]+w+dis[1][v]=dis[0][t]$(t表示终点)。如果在,就把它加入网络流图中,**流量为两端点中吞吐量较小的一个**。这种做法看上去没有问题,因为两个点相连新吞吐量依赖于较低的点的吞吐量。
不过一个点**不一定只有这一条流连接**,当有多条流流入且有多条流流出时,它的流量可以被**扩充**超过它的吞吐量。比如说十字路口这种图:
![](http://www.wjyyy.top/wp-content/uploads/2018/07/201807071657.png)所有点的吞吐量均为1。
即使4号点的吞吐量为1,也只能构建出这样的图,而这时最大流为2,不符合题意。当这个十字路口变为度为2k的点时,它的流量可以达到吞吐量×k。
可能是数据不够强,致使我这种非完美解法能通过。
# 正确解法:
把一个点拆成两个,一个管进入,一个管流出,两个点之间以吞吐量为流量的边连接起来。再把最短路上满足条件的点(分拆点的进出)相连,权值为inf。直接跑1到n的最大流,最大流就是答案了。
贴一下非完美解法的Code,完美解法参考其他dalao的题解。
## Code:
```cpp
#include<cstdio>
#include<cstring>
#include<queue>
using std::deque;
int min(int x,int y)
{
return x<y?x:y;
}
namespace graph//建了两个图所以用命名空间
{
struct edge
{
int n;
int v;
int nxt;
edge(int n,int v,int nxt)
{
this->n=n;
this->v=v;
this->nxt=nxt;
}
edge()
{
nxt=-1;
}
}e[210000];
int head[501],cnt=-1;
void add(int from,int to,int v)
{
e[++cnt]=edge(to,v,head[from]);
head[from]=cnt;
e[++cnt]=edge(from,v,head[to]);
head[to]=cnt;
}
void init()
{
memset(head,-1,sizeof(head));
}
long long dis[2][510];
void spfa(int x)
{
deque<int> q;
bool used[510];
memset(used,0,sizeof(used));
memset(dis[x!=1],0x3f,sizeof(dis[x!=1]));
used[x]=1;
dis[x!=1][x]=0;
int flag=(x!=1);
q.push_back(x);
while(!q.empty())
{
int k=q.front();
q.pop_front();
used[k]=false;
for(int i=head[k];~i;i=e[i].nxt)
{
if(dis[flag][e[i].n]>dis[flag][k]+e[i].v)
{
dis[flag][e[i].n]=dis[flag][k]+e[i].v;
if(!used[e[i].n])
{
if(q.empty()||dis[flag][e[i].n]<dis[flag][q.front()])
q.push_front(e[i].n);
else
q.push_back(e[i].n);
used[e[i].n]=true;
}
}
}
}
}
}
int flow[510];
long long sum=0;//要开long long
namespace Flow
{
struct edge
{
int n,v;
int nxt;
edge(int n,int v,int nxt)
{
this->n=n;
this->v=v;
this->nxt=nxt;
}
edge()
{
nxt=-1;
}
}e[210000];
int head[505],cnt=-1;
void add(int from,int to,int v)
{
e[++cnt]=edge(to,v,head[from]);
head[from]=cnt;
e[++cnt]=edge(from,0,head[to]);
head[to]=cnt;
}
void init()
{
memset(head,-1,sizeof(head));
}
int d[505],gap[505];
void bfs(int x)
{
memset(d,0,sizeof(d));
int q[505],l=0,r=0;
q[++r]=x;
d[x]=1;
gap[0]=123456;
while(l<r)
{
int k=q[++l];
for(int i=head[k];~i;i=e[i].nxt)
{
if(!d[e[i].n])
{
d[e[i].n]=d[k]+1;
gap[d[e[i].n]]++;
q[++r]=e[i].n;
}
}
}
}
void isap(int x)//x表示有多少个点
{
bfs(x);
int s=1;
int pre[505];
memset(pre,-1,sizeof(pre));
int cur[505];
for(int i=1;i<=x;i++)
cur[i]=head[i];
while(d[1]<=x)
{
if(s==x)
{
int minn=1234567890;
int p=pre[s];
while(~p)
{
minn=min(minn,e[p].v);
p=pre[e[p^1].n];
}
sum+=minn;
p=pre[s];
while(~p)
{
e[p].v-=minn;
e[p^1].v+=minn;
p=pre[e[p^1].n];
}
s=1;
}
int flag=0;
for(int i=cur[s];~i;i=e[i].nxt)
if(e[i].v&&d[e[i].n]+1==d[s])
{
pre[e[i].n]=i;
cur[s]=e[i].nxt;
flag=1;
s=e[i].n;
break;
}
if(flag==0)
{
int tmp=d[s];
d[s]=x+1;
for(int i=head[s];~i;i=e[i].nxt)
if(e[i].v)
d[s]=min(d[s],d[e[i].n]+1);
gap[tmp]--;
gap[d[s]]++;
if(gap[tmp]==0)
return;
cur[s]=head[s];
if(s!=1)
s=e[pre[s]^1].n;
}
}
}
}
int main()
{
using namespace graph;
init();
Flow::init();
int n,m,u,v,w;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
for(int i=1;i<=n;i++)
scanf("%d",&flow[i]);
flow[1]=1234567890;
flow[n]=1234567890;
spfa(1);
spfa(n);
for(int i=1;i<=n;i++)
for(int j=head[i];~j;j=e[j].nxt)
if(dis[0][i]+e[j].v+dis[1][e[j].n]==dis[0][n])
Flow::add(i,e[j].n,min(flow[i],flow[e[j].n]));
Flow::isap(n);
printf("%lld\n",sum);
return 0;
}
```