「转载」最大流
- C/C++ code
/* 题目：poj 1273 Drainage Ditches (网络流最大流) 题意： 有n道水渠,和m个节点,其中每道水渠都有一个最大流 问从1节点到m节点的最大流 Sample Input 5 4 1 2 40 1 4 20 2 4 20 2 3 30 3 4 10 Sample Output 50 解题： 最大流 利用 edmonds_karp算法 bfs */#include<stdio.h> #include<string.h> #define M 230 #define INF 0x7FFFFFFF #define min(a,b) a<b?(a):(b) /* f[i]存储第i点存储的水 residual[i][j]存储从i到j水渠的剩余流量 pre存储前驱节点*/ int residual[M][M],pre[M],f[M],q[M]; int n,m; void input() { int x,y,z; memset(residual,0,sizeof(residual)); for(int i=0;i<n;i++) { scanf("%d%d%d",&x,&y,&z); residual[x][y]+=z;/* 因为存在回路 */ } } int bfs() { for(int i=1;i<=m;i++) f[i]=INF; q[0]=1; memset(pre,-1,sizeof(pre)); int head=-1,tail=0,cur; while(head<tail) { ++head; cur=q[head]; if(cur==m) return f[m]; for(int i=1;i<=m;i++) { /*如果该点已经走过或者从cur到i的水渠的流量为0时*/ if(pre[i]!=-1||residual[cur][i]==0) continue; pre[i]=cur; f[i]=min(f[cur],residual[cur][i]); ++tail; q[tail]=i; } } return -1; } int EK() { int ans=0; while(1) { int tmp=bfs(); if(tmp==-1) return ans; ans+=tmp; int a=m; int b; while(a!=1) { b=pre[a]; residual[b][a]-=tmp;/* 正向流减小 */ residual[a][b]+=tmp;/* 反向流增加 */ a=b; } } } int main() { while(scanf("%d%d",&n,&m)==2) { input(); printf("%d\n",EK()); } return 0; }[解决办法]
我是这样想的
首先将每个人做不同工作的收益做一个最大堆 堆里面每个元素包含如下信息，工作序号及做这项工作所得的收益 这个堆就根据收益来排序，这样我们就得到了n个最大堆，然后再根据每个堆的顶来构建一个结构体 这个结构体包含了 人的序号，工作的序号，做这项工作的收益，然后再根据收益对这n个结构体来排序建立一个最大堆 ，每次从这个最大堆里面提取最大的一个元素，输出这个元素，然后再根据元素的工作序号对这个堆的剩余元素进行扫描，如果碰到工作序号相同的就对这个元素所代表的堆进行一次提取，但不输出，更新元素的值，然后再对这个元素下移到正确的位置，扫描完之后，再对这个堆进行提取，重复上述步骤，直到大堆中没有小堆为止
对每个小堆进行建堆 lg(n) 建堆所花时间n*lg(n)
建大堆花时间lg(n);
每次提取花时间lg(n)，扫描花时间n/2(平均）如果碰到有序号相同的 则需要对小堆进行提取 花时间lg(n) 最多耗时n*lg(n)
n次提取耗时上限为n*（lg(n)+n/2+lg(n)*n)
所以总时间上线为lg(n)*(n+1)*(n+1) +n*n/2
不知道这个方法有没有效果
[解决办法]
楼主心态不端正