初识网络流（EK and Dinic 模板）(2) - Linux安全网 - Linux操作系统_Linux 命令_Linux教程

初识网络流（EK and Dinic 模板）(2)

日期:2011-08-14 点击:26 来源: 未知分享至:

{
34 /*查找最小增流的时候，只查找最短路径上的点*/
35 flow=INF;
36 tmp=N+1; //tmp 等于总得点数
37 while(tmp!= 0)
38 {
39 if(map[pre[tmp]][tmp]<flow)
40 flow=map[pre[tmp]][tmp];
41 tmp = pre[tmp];
42 }
43 maxFlow+=flow;
44 tmp=N+1;
45 while(tmp!=0) //0的意思是代表源点
46 {
47 map[pre[tmp]][tmp]-=flow;
48 map[tmp][pre[tmp]]+=flow;
49 tmp=pre[tmp];
50 }
51 }
52 printf(\"%dn\",maxFlow);
53 } 下面是Dinic！速度相对较快！就是代码复杂

View Code

 1 const int maxn=150000;
 2 const int maxm=200000;
 3 const int inf=1<<30;
 4 struct edge
 5 {
 6     int from,to,val,next;
 7 }map[maxn];
 8 int vis[maxn],que[maxn],dist[maxn],len;
 9 void init()
10 {
11     len=0;
12     memset(vis,-1,sizeof(vis));
13 }
14 void insert (int from,int to,int val)
15 {
16     map[len].from=from,map[len].to=to,map[len].val=val;
17     map[len].next=vis[from];
18     vis[from]=len++;
19     map[len].from=to,map[len].to=from,map[len].val=0;
20     map[len].next=vis[to];
21     vis[to]=len++;
22 }
23 int Dinic(int n,int s,int t)
24 {
25     int

Tags：

分享至: