最大流Dinic C语言实现（详细）--poj 3281

本文主要是介绍最大流Dinic C语言实现（详细）--poj 3281，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

//Dinic最大的不同就是分层找增长路径。。。，
//我们知道一般是用BFS来找一个增长路径，从中心一层一层地向外扩散
//但是Dinic也是一层一层的向外找，但是它每层只选择一个一个顶点就跳到下一层中接着寻找
#include<stdio.h>
#define N 1000
#define MAX 0x3f3f3f3f
#define min(x,y) ((x>y)?(y):(x))//定义宏
int map[N][N];//图
int dis[N];//来表示分层图距离
int q[10000],h,r;//手工队列，h为队首，r为队尾
int source,sink;//顶点的最大编号sink，最小编号source=0
int BFS(void)
{int i,j;memset(dis,0xff,sizeof(dis));dis[0]=0;h=-1;r=0;q[0]=0;while(h<r){j=q[++h];for(i=0;i<=sink;i++){if(dis[i]<0&&map[j][i]>0){dis[i]=dis[j]+1;//来决定每个点与源点的距离，也就是分层。。。q[++r]=i;}}}if(dis[sink]>0)return 1;elsereturn 0;
}
int find(int x,int low)//表示已经到了x顶点，并且此时从源点到x顶点的这一段路中可以达到的最大流量
{int i,a=0;if(x==sink)//如果到了汇点，返回最大流量return low;for(i=0;i<=sink;i++){if(map[x][i]>0&&dis[i]==dis[x]+1&&(a=find(i,min(low,map[x][i]))))//这就是每一层找一个，然后接着找下一层{map[x][i]-=a;//正向边流量增加map[i][x]+=a;//反向边流量减少return a;}}return 0;
}
int main()
{int ans,tans,n,f,d,i,f_sum,d_sum,j,tmp;while(~scanf("%d%d%d",&n,&f,&d)){memset(map,0,sizeof(map));source=0;sink=2*n+f+d+1;for(i=1;i<=f;i++)map[source][i]=1;//构建图，这道题有点特殊的构图方式for(i=1;i<=d;i++)map[2*n+f+i][sink]=1;for(i=1;i<=n;i++)map[f+i][f+n+i]=1;for(i=1;i<=n;i++){scanf("%d%d",&f_sum,&d_sum);for(j=1;j<=f_sum;j++){scanf("%d",&tmp);map[tmp][f+i]=1;}for(j=1;j<=d_sum;j++){scanf("%d",&tmp);map[f+n+i][2*n+f+tmp]=1;}}ans=0;while(BFS()){while(tans=find(0,0x3f3f3f3f))ans+=tans;}printf("%d\n",ans);}
}

//还有一种实现方式，这是从汇点开始到源点结束的。。。。。
#define MAXV 410
#define INF INT_MAX
#define min(a,b) (a>b?b:a)
int res[MAXV][MAXV];		
int	dis[MAXV];			
int n,maxflow;	
int bfs(){int k;queue<int> q;memset(dis,-1,sizeof(dis));dis[n]=0;q.push(n);while(!q.empty()){k=q.front();q.pop();for(int i=0;i<n;i++){if(dis[i]==-1 && res[i][k]){dis[i] = dis[k] + 1;q.push(i);}}if(k==0) return 1;}return 0;
}int dfs(int cur,int cp){if(cur==n)	return cp;int tmp=cp,t;for(int i=0;i<=n && tmp;i++){if(dis[i]+1==dis[cur] && res[cur][i]){t=dfs(i,min(res[cur][i],tmp));res[cur][i]-=t;res[i][cur]+=t;tmp-=t;}}return cp-tmp;
}

这篇关于最大流Dinic C语言实现（详细）--poj 3281的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---