题解 P3171 【[CQOI2015]网络吞吐量】 非完美解法

wjyyy

2018-07-07 17:08:39

Solution

来发一篇非完美解法的题解;[我的博客](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; } ```