网络流入门
Published On September 20, 2015
基本定义
算法导论上也有相关知识，最大流基本的算法就一种，但是实现的方法可能有很多。
poj 1273 Drainage Ditches
-
题目大意: 给一个有向图，求最大流。在上面的链接中讲到。
-
思路: 建图，每次用bfs()找增广路，注意bfs的过程中到下一个节点的流量必须大于0。如果bfs()到不了汇点则退出。
#include <iostream>
#include <queue>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
const int V = 203;
int map[V][V],flow[V],path[V],start,end;
const int INF = 1000000000;
int m,n,a,b,c;
int bfs()
{
int s,t;
flow[start]=INF;
memset(path,-1,sizeof(path));
path[start]=start;
queue<int> Q;
Q.push(start);
while(!Q.empty())
{
s=Q.front();
Q.pop();
for(int i=1;i<=n;i++)
{
t=i;
if(path[t]==-1 && map[s][t]>0)// map[s][t] must have capacity or t will not in queue
{
flow[t]=flow[s]<map[s][t]?flow[s]:map[s][t];
Q.push(t);
path[t]=s;
}
}
}
if(path[end]==-1)
return -1;
return flow[end];
}
int Edmonds_Karp()
{
int max_flow=0,step,current,next;
memset(flow,0,sizeof(flow));
while((step=bfs())!=-1)
{
max_flow+=step;
current=end;
while(current!=start)
{
next=path[current];
map[current][next]+=step;
map[next][current]-=step;
current=path[current];
}
}
return max_flow;
}
int main()
{
while(~scanf("%d%d",&m,&n))
{
memset(map,0,sizeof(map));
start=1;
end=n;
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
map[a][b]+=c;
}
printf("%d\n", Edmonds_Karp());
}
}poj 1459 Power Network
- 解题思路: 跟上题一样，只要建图对了就能过
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
char t[1000];
const int V = 103;
const int INF = 1000000000;
int n,np,nc,m,len,map[V][V],p[V],c[V],flow[V],path[V],start,end,next,current,s;
int bfs()
{
flow[start]=INF;
memset(path,-1,sizeof(path));
queue<int> Q;
Q.push(start);
path[start]=start;
while(!Q.empty())
{
s=Q.front();
Q.pop();
for(int i=2;i<=end;i++)
{
if(path[i]==-1 && map[s][i])
{
flow[i]=min(flow[s],map[s][i]);
// printf("s= %d i= %d flow[i]= %d \n",s,i,flow[i]);
path[i]=s;
Q.push(i);
}
}
}
if(path[end]==-1)
return -1;
return flow[end];
}
int Edmonds_Karp()
{
int max_flow=0,step;
start=1;
end=n+2;
while((step=bfs())!=-1)
{
// printf("step= %d\n",step);
max_flow+=step;
current=end;
while(current!=start)
{
next=path[current];
map[current][next]+=step;
map[next][current]-=step;
current=next;
}
}
return max_flow;
}
void init()
{
memset(map,0,sizeof(map));
memset(p,0,sizeof(p));
memset(c,0,sizeof(c));
}
int main()
{
while(~scanf("%d%d%d%d",&n,&np,&nc,&m))
{
init();
for(int j=0;j<m;j++)
{
scanf("%s",t);
len=strlen(t);
int i=1;
int a=0;
while(t[i]!=',')
{
a=a*10+t[i]-'0';
i++;
}
i++;
int b=0;
while(t[i]!=')')
{
b=b*10+t[i]-'0';
i++;
}
i++;
int c=0;
while(i<len)
{
c=c*10+t[i]-'0';
i++;
}
map[a+2][b+2]=c;
}
for(int j=0;j<np;j++)
{
scanf("%s",t);
len=strlen(t);
int i=1;
int a=0;
while(t[i]!=')')
{
a=a*10+t[i]-'0';
i++;
}
i++;
int b=0;
while(i<len)
{
b=b*10+t[i]-'0';
i++;
}
p[a+2]=b;
}
for(int j=0;j<nc;j++)
{
scanf("%s",t);
len=strlen(t);
int i=1;
int a=0;
while(t[i]!=')')
{
a=a*10+t[i]-'0';
i++;
}
i++;
int b=0;
while(i<len)
{
b=b*10+t[i]-'0';
i++;
}
c[a+2]=b;
}
for(int i=2;i<2+n;i++)
{
if(p[i]>0)
map[1][i]=p[i];
if(c[i]>0)
map[i][n+2]=c[i];
}
printf("%d\n",Edmonds_Karp());
}
}poj 1637 Sightseeing tour
-
题目大意: 给一张图，N个点M条边.从一个城市出发，经过每条路一次且仅一次，而且要求最后回到原点.求是否存在可行的方案(在审题的时候有个坑:the streets are either one-way or two-way 意为某条路要么是单行道,只能从xi走到yi;要么是双行道,既能从xi走到yi,又能从yi走到xi,但是由于一条路只能走一次的约束，我们只能选择从其中一个点走到另一个点。)
-
思路：求混合图是否有欧拉回路(结论:有向边的欧拉回路意味着一个方案中，每个点的出度和入度都相同)。先是基图联通（不考虑度为0的点），然后需要借助网络流来判断。
-
实现: -先将双向边假设一个走向(任意)。统计每个点的di，如果存在d[i]为奇数，那么方案一定不存在，因为就算改变边的方向，入度+1出度-1，d[i]依然为奇数。 -建图，对于源点连接所有d[i]>0的点，容量为-d[i]/2;汇点连接所有d[i]<0的点，容量为d[i]/2。然后跑网络流，如果满流则possible
#include <iostream>
#include <queue>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int V = 203;
int map[V][V],flow[V],path[V],start,end,out[V],in[V],target;
bool flag;
const int INF = 1000000000;
int m,n,a,b,c;
int bfs()
{
int s,t;
flow[start]=INF;
memset(path,-1,sizeof(path));
path[start]=start;
queue<int> Q;
Q.push(start);
while(!Q.empty())
{
s=Q.front();
Q.pop();
for(int i=1;i<=end;i++)
{
t=i;
if(path[t]==-1 && map[s][t]>0)// map[s][t] must have capacity or t will not in queue
{
flow[t]=flow[s]<map[s][t]?flow[s]:map[s][t];
// printf("s= %d t= %d\n",s,t);
// printf("flow t= %d\n",flow[t]);
Q.push(t);
path[t]=s;
}
}
}
if(path[end]==-1)
return -1;
return flow[end];
}
int Edmonds_Karp()
{
int max_flow=0,step,current,next;
memset(flow,0,sizeof(flow));
while((step=bfs())!=-1)
{
// printf("step= %d\n",step);
max_flow+=step;
current=end;
while(current!=start)
{
next=path[current];
map[current][next]+=step;
map[next][current]-=step;
current=path[current];
}
}
return max_flow;
}
int main()
{
int _;
scanf("%d",&_);
while(_--)
{
scanf("%d%d",&n,&m);
memset(map,0,sizeof(map));
memset(out,0,sizeof(out));
memset(in,0,sizeof(in));
flag=true;
start=1;
end=n+2;
target=0;
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
out[a+1]++;
in[b+1]++;
if(c==0)
map[a+1][b+1]+=1;
}
for(int i=2;i<=n+1;i++)
{
if(out[i]>in[i])
{
if((out[i]-in[i])%2==1){
flag=false;
break;
}
map[start][i]=(out[i]-in[i])/2;
target+=(out[i]-in[i])/2;
}
if(in[i]>out[i])
{
if((in[i]-out[i])%2==1){
flag=false;
break;
}
map[i][end]=(in[i]-out[i])/2;
target+=(in[i]-out[i])/2;
}
}
// for(int i=1;i<=5;i++)
// {
// for(int j=1;j<=5;j++)
// printf("%d",map[i][j]);
// printf("\n");
// }
// printf("Edmonds_Karp= %d\n", Edmonds_Karp());
// printf("target= %d\n", target);
if(!flag){
printf("impossible\n");
continue;
}
if(Edmonds_Karp()==target/2)
printf("possible\n");
else
printf("impossible\n");
}
}hdu 4862 Jump
-
题意: n*m的格子，每个格子有0~9的权值。你的初始能量是0.你最多玩K次(但是可以只玩小于K次就不玩了)。你每回合玩都需要选择一个没到过的格子开始，然后开始跳(可以往左跳也可以往下跳，跨度可以不止一个格子，但是跳到的格子也必须是以前从来没有经过的)。只要你不违反以上的规则，每回合你跳的次数没有限制。每一跳都会消耗|x1-x2|+|y1-y2|-1 的体力，体力值可以为负。在每次跳跃中，如果开始点和结束点的权值相同，比如都为S，那么你获得值为S的体力。问，是否有一种方案能经过每个点一次且仅一次而且使你的体力值最大？
-
先吐槽一句，题目规则挺复杂的，读了好久，还好样例比较良心，读懂了样例就没有问题了，接下来就是建图了。
-
建图: 思路非常巧妙，构造二部图，X部有NM个节点，源点向X部每个节点连一条边，流量1，费用0，Y部有NM个节点，每个节点向汇点连一条边，流量1，费用0，如果X部的节点x可以在一步之内到达Y部的节点y，那么就连边x->y，费用为从x格子到y格子的花费能量减去得到的能量，流量1，再在X部增加一个新的节点，表示可以从任意节点出发K次，源点向其连边，费用0，流量K，这个点向Y部每个点连边，费用0，流量1，最这个图跑最小费用最大流，如果满流就是存在解，反之不存在，最小费用的相反数就是可以获得的最大能量
-
思考: 这样建图的意义是什么呢？如果从X部的点i到Y部的j流量为1(流量只能为0或1)，那么说明从X直接跳到了Y。从新的节点tmp到Y部某点i的流量为1，说明i为一回合的起点。如果从Y部的一个节点i到汇点T流量为1，说明i被经过了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
char mp[15][15];
const int V = 1001;
struct e
{
int v,cap,cost,nxt;
}e[10001];
const int INF = 1000000000;
int dis[V],pre[V],g[V],cnt,n,st,en,tmp,s,t,c,N,M,K,now,flow_once,p,res,sum_flow,vis[V],que[V];
// undirect edge
void add(int u,int v,int cap,int cost)
{
e[++cnt].v=v;
e[cnt].cap=cap;
e[cnt].cost=cost;
e[cnt].nxt=g[u];
g[u]=cnt;
e[++cnt].v=u;
e[cnt].cap=0;
e[cnt].cost=-cost;
e[cnt].nxt=g[v];
g[v]=cnt;
}
bool spfa()
{
for(int i=0;i<=n;i++)
{
dis[i]=INF;
vis[i]=false;
}
dis[st]=0;
vis[st]=true;
queue<int> Q;
Q.push(st);
while(!Q.empty())
{
s=Q.front();
Q.pop();
vis[s]=false;
for(int idx=g[s];idx;idx=e[idx].nxt)
{
t=e[idx].v;
if(e[idx].cap && dis[t]>dis[s]+e[idx].cost)
{
// printf("t= %d in\n", t);
// printf("pre= %d\n", pre[t]);
dis[t]=dis[s]+e[idx].cost;
if(vis[t]==false){
Q.push(t);
vis[t]=true;
}
pre[t]=idx;
}
}
}
// printf("pre en = %d\n", pre[en]);
if(dis[en]==INF)return false;
else return true;
}
void init()
{
cnt=1;
res=0;
n=N*M;
st=2*n;
en=st+1;
tmp=en+1;
sum_flow=0;
memset(g,0,sizeof(g));
add(st,tmp,K,0);
for(int i=0;i<n;i++)
{
add(st,i,1,0);
add(i+n,en,1,0);
add(tmp,i+n,1,0);
}
for(int i=0;i<N;i++)
{
for(int j=0;j<M;j++)
{
now=i*M+j;
for(int k=i+1;k<N;k++)
{
c=k-i-1;
if(mp[i][j]==mp[k][j])
c-=mp[i][j]-'0';
add(now,k*M+j+n,1,c);
}
for(int k=j+1;k<M;k++)
{
c=k-j-1;
if(mp[i][j]==mp[i][k])
c-=mp[i][j]-'0';
add(now,i*M+k+n,1,c);
}
}
}
n=tmp;// the meaning of n later is the number of points in the graph
}
int MCMF()
{
init();
while(spfa())
{
flow_once=INF;
for(int current=en;current!=st;current=e[p^1].v)
{
p=pre[current];
flow_once=min(flow_once,e[p].cap);
}
// printf("flow= %d\n", flow_once);
for(int current=en;current!=st;current=e[p^1].v)
{
p=pre[current];
e[p].cap-=flow_once;
e[p^1].cap+=flow_once;
res+=flow_once*e[p].cost;
// printf("%d ", current);
}
// printf("\n");
// printf("res= %d\n",res);
sum_flow+=flow_once;
}
if(sum_flow!=N*M)
return -1;
return -res;
}
int main()
{
int _;
scanf("%d",&_);
for(int ii=1;ii<=_;ii++)
{
scanf("%d%d%d",&N,&M,&K);
for(int i=0;i<N;i++)
scanf("%s",mp[i]);
printf("Case %d : %d\n",ii, MCMF());
}
}Tags: Algorithm