G - Island Transport（双向边最大流）

71 阅读 0 评论 47 点赞

我是靠谱客的博主超级鼠标，最近开发中收集的这篇文章主要介绍G - Island Transport（双向边最大流），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

In the vast waters far far away, there are many islands. People are living on the islands, and all the transport among the islands relies on the ships.
　　You have a transportation company there. Some routes are opened for passengers. Each route is a straight line connecting two different islands, and it is bidirectional. Within an hour, a route can transport a certain number of passengers in one direction. For safety, no two routes are cross or overlap and no routes will pass an island except the departing island and the arriving island. Each island can be treated as a point on the XY plane coordinate system. X coordinate increase from west to east, and Y coordinate increase from south to north.
　　The transport capacity is important to you. Suppose many passengers depart from the westernmost island and would like to arrive at the easternmost island, the maximum number of passengers arrive at the latter within every hour is the transport capacity. Please calculate it.
Input
　　The first line contains one integer T (1<=T<=20), the number of test cases.
　　Then T test cases follow. The first line of each test case contains two integers N and M (2<=N,M<=100000), the number of islands and the number of routes. Islands are number from 1 to N.
　　Then N lines follow. Each line contain two integers, the X and Y coordinate of an island. The K-th line in the N lines describes the island K. The absolute values of all the coordinates are no more than 100000.
　　Then M lines follow. Each line contains three integers I1, I2 (1<=I1,I2<=N) and C (1<=C<=10000) . It means there is a route connecting island I1 and island I2, and it can transport C passengers in one direction within an hour.
　　It is guaranteed that the routes obey the rules described above. There is only one island is westernmost and only one island is easternmost. No two islands would have the same coordinates. Each island can go to any other island by the routes.
Output
　　For each test case, output an integer in one line, the transport capacity.
　　题面是一道裸的最大流，给出n个点和m条双向边，点以坐标表示，横坐标最小的是源点，最大的是汇点。按照题目建边跑最大流即可，不过题目里给出的是双向边，所以在建立反向边是要注意容量不是0，而是和正向边一样，然后跑最大流。
　　不过要注意普通dinic算法会超时，所以这里用的ISAP

#include<stdio.h>
#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1e5+5;
const int maxm=1e5+5;
int head[maxn],cur[maxn],dep[maxn],ne,pre[maxn],num[maxn],n,m,S,T,maxflow;
queue<int> q;
struct edge
{
int next,to,cost;
}e[maxm*2];
void add(int u,int v,int w)
{
e[ne].to=v;
e[ne].cost=w;
e[ne].next=head[u];
head[u]=ne++;
e[ne].to=u;
e[ne].cost=w;
e[ne].next=head[v];
head[v]=ne++;
}
void bfs(int t)
{
while(!q.empty()) q.pop();
for(int i=1;i<=n;i++) cur[i]=head[i];
for(int i=1;i<=n;i++) dep[i]=n;
dep[t]=0;
q.push(t);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i!=-1;i=e[i].next)
{
if(dep[e[i].to]==n&&e[i^1].cost)
{
dep[e[i].to]=dep[u]+1;
q.push(e[i].to);
}
}
}
}
int addflow(int s,int t)
{
int ans=INF,u=t;
while(u!=s)
{
ans=min(ans,e[pre[u]].cost);
u=e[pre[u]^1].to;
}
u=t;
while(u!=s)
{
e[pre[u]].cost-=ans;
e[pre[u]^1].cost+=ans;
u=e[pre[u]^1].to;
}
return ans;
}
void ISAP(int s,int t)
{
int u=s;
bfs(t);
for(int i=1;i<=n;i++) num[dep[i]]++;
while(dep[s]<n)
{
if(u==t)
{
maxflow+=addflow(s,t);
u=s;
}
int flag=0;
for(int &i=cur[u];i!=-1;i=e[i].next)
{
if(dep[u]==dep[e[i].to]+1&&e[i].cost)
{
flag=1;
pre[e[i].to]=i;
u=e[i].to;
break;
}
}
if(!flag)
{
int minn=n-1;
for(int i=head[u];i!=-1;i=e[i].next)
{
if(e[i].cost)
{
minn=min(minn,dep[e[i].to]);
}
}
if((--num[dep[u]])==0) break;
dep[u]=minn+1;
num[dep[u]]++;
cur[u]=head[u];
if(u!=s) u=e[pre[u]^1].to;
}
}
}
void init()
{
memset(head,-1,sizeof(head));
ne=0;
memset(num,0,sizeof(num));
maxflow=0;
}
struct island
{
int x,y;
}is[maxm];
int main()
{
int tt;
scanf("%d",&tt);
while(tt--)
{
scanf("%d%d",&n,&m);
init();
S=0;
T=n+1;
int minn=1e5+5,maxx=-minn;
for(int i=1;i<=n;i++)
{
int x,y;
scanf("%d%d",&is[i].x,&is[i].y);
if(minn>is[i].x)
{
minn=is[i].x;
S=i;
}
if(maxx<is[i].x)
{
maxx=is[i].x;
T=i;
}
}
for(int i=0;i<m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
ISAP(S,T);
printf("%dn",maxflow);
}
}

另外用最高标号预流推进还能再快很多

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using std::min;
using std::vector;
using std::queue;
using std::priority_queue;
const int N=2e5+5,M=2e5+5,inf=0x3f3f3f3f;
int n,s,t,tot;
int v[M<<1],w[M<<1],first[N],next[M<<1];
int h[N],e[N],gap[N<<1],inq[N];//节点高度是可以到达2n-1的
void init()
{
tot=0;
memset(first,0,sizeof(first));
memset(h,0,sizeof(h));
memset(e,0,sizeof(e));
memset(gap,0,sizeof(gap));
memset(inq,0,sizeof(inq));
}
struct cmp
{
inline bool operator()(int a,int b) const
{
return h[a]<h[b];//因为在优先队列中的节点高度不会改变，所以可以直接比较
}
};
queue<int> Q;
priority_queue<int,vector<int>,cmp> pQ;
inline void add_edge(int from,int to,int flow)
{
tot+=2;
v[tot+1]=from;v[tot]=to;w[tot]=flow;w[tot+1]=flow;
next[tot]=first[from];first[from]=tot;
next[tot+1]=first[to];first[to]=tot+1;
return;
}
inline bool bfs()
{
int now;
register int go;
memset(h+1,0x3f,sizeof(int)*n);
h[t]=0;Q.push(t);
while(!Q.empty())
{
now=Q.front();Q.pop();
for(go=first[now];go;go=next[go])
if(w[go^1]&&h[v[go]]>h[now]+1)
h[v[go]]=h[now]+1,Q.push(v[go]);
}
return h[s]!=inf;
}
inline void push(int now)//推送
{
int d;
register int go;
for(go=first[now];go;go=next[go])
if(w[go]&&h[v[go]]+1==h[now])
{
d=min(e[now],w[go]);
w[go]-=d;w[go^1]+=d;e[now]-=d;e[v[go]]+=d;
if(v[go]!=s&&v[go]!=t&&!inq[v[go]])
pQ.push(v[go]),inq[v[go]]=1;
if(!e[now])//已经推送完毕可以直接退出
break;
}
return;
}
inline void relabel(int now)//重贴标签
{
register int go;
h[now]=inf;
for(go=first[now];go;go=next[go])
if(w[go]&&h[v[go]]+1<h[now])
h[now]=h[v[go]]+1;
return;
}
inline int hlpp()
{
int now,d;
register int i,go;
if(!bfs())//s和t不连通
return 0;
h[s]=n;
memset(gap,0,sizeof(int)*(n<<1));
for(i=1;i<=n;i++)
if(h[i]<inf)
++gap[h[i]];
for(go=first[s];go;go=next[go])
if(d=w[go])
{
w[go]-=d;w[go^1]+=d;e[s]-=d;e[v[go]]+=d;
if(v[go]!=s&&v[go]!=t&&!inq[v[go]])
pQ.push(v[go]),inq[v[go]]=1;
}
while(!pQ.empty())
{
inq[now=pQ.top()]=0;pQ.pop();push(now);
if(e[now])
{
if(!--gap[h[now]])//gap优化，因为当前节点是最高的所以修改的节点一定不在优先队列中，不必担心修改对优先队列会造成影响
for(i=1;i<=n;i++)
if(i!=s&&i!=t&&h[i]>h[now]&&h[i]<n+1)
h[i]=n+1;
relabel(now);++gap[h[now]];
pQ.push(now);inq[now]=1;
}
}
return e[t];
}
int m;
struct island
{
int x,y;
}is[M];
signed main()
{
int tt;
scanf("%d",&tt);
while(tt--)
{
scanf("%d%d",&n,&m);
init();
s=0;
t=n+1;
int minn=1e5+5,maxx=-minn;
for(int i=1;i<=n;i++)
{
int x,y;
scanf("%d%d",&is[i].x,&is[i].y);
if(minn>is[i].x)
{
minn=is[i].x;
s=i;
}
if(maxx<is[i].x)
{
maxx=is[i].x;
t=i;
}
}
for(int i=0;i<m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add_edge(x,y,z);
}
printf("%dn",hlpp());
}
return 0;
}