我要啦免费统计
最大流
http://acm.pku.edu.cn/JudgeOnline/problem?id=1273

#include
<iostream>
using namespace std;

#define MAXN 210
#define inf 2110000000
int con[MAXN][MAXN];
int f[MAXN][MAXN]; 
//求网络最大流,邻接阵形式
//返回最大流量,flow返回每条边的流量
//传入网络节点数n,容量mat,源点source,汇点sink

int max_flow(int n,int mat[][MAXN],int source,int sink,int flow[][MAXN])
{
    
    
int pre[MAXN],que[MAXN],d[MAXN],p,q,t,i,j;
    
if (source==sink) return inf;
    
for (i=0;i<n;i++)
        
for (j=0;j<n;flow[i][j++]=0);
        
    
while(1){
        
for (i=0;i<n;pre[i++]=0);
        pre[t
=source]=source+1,d[t]=inf;
        
for (p=q=0;p<=q&&!pre[sink];t=que[p++])
            
for (i=0;i<n;i++)
                
if (!pre[i]&&(j=mat[t][i]-flow[t][i]))
                    pre[que[q
++]=i]=t+1,d[i]=d[t]<j?d[t]:j;
                
else if (!pre[i]&&(j=flow[i][t]))
                    pre[que[q
++]=i]=-t-1,d[i]=d[t]<j?d[t]:j;
        
if (!pre[sink]) break;
        
for (i=sink;i!=source;)
            
if (pre[i]>0)
                flow[pre[i]
-1][i]+=d[sink],i=pre[i]-1;
            
else
                flow[i][
-pre[i]-1]-=d[sink],i=-pre[i]-1;
    }
    
for (j=i=0;i<n;j+=flow[source][i++]);
    
return j;
}

int main()
{
    
int n,m;
    
int a,b,c;
    
    
while(scanf("%d%d",&m,&n)!=EOF){
       memset(con,
0,sizeof(con));
       
for(int i=0;i<m;i++){
         scanf(
"%d%d%d",&a,&b,&c);
         con[a
-1][b-1]+=c;
       }
       printf(
"%d\n",max_flow(n,con,0,n-1,f));
    }
    
return 0;
}

posted on 2009-02-14 15:31 阅读(597) 评论(1)  编辑 收藏 引用 所属分类: pku

评论:
# re: pku 1273 Drainage Ditches 2009-02-14 23:59 | weitao
谢谢哈  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理