Drolca

Apologize To Drolca
随笔 - 28, 文章 - 1, 评论 - 6, 引用 - 0
数据加载中……

有一个悲剧...最小点割

 

#include <iostream>
using namespace std;
const int maxn=200;
const int INF=1000000;
int g[maxn][maxn];
int f[maxn][maxn];
int r[maxn][maxn];

int Edmonds_Karp(int n,int g[][maxn],int s,int t,int f[][maxn]) 

    
int i,j,k,c,head,tail,flow=0 ; 
    
int prev[maxn],visit[maxn],q[maxn]; 
    
for(i=0;i<n;i++)for(j=0;j<n;j++
    

        f[i][j]
=0 ; 
        r[i][j]
=g[i][j]; 
    }
 
    
while(1
    

        head
=tail=0 ; 
        memset(visit,
0,sizeof(visit)); 
        q[tail
++]=s ; 
        prev[s]
=-1 ; 
        visit[s]
=1 ; 
        
while(head<tail) 
        

            k
=q[head++]; 
            
for(i=0;i<n;i++)
                
if(!visit[i]&&r[k][i]>0
                

                    visit[i]
=1 ; 
                    prev[i]
=k ; 
                    
if(i==t)goto next ; 
                    q[tail
++]=i ; 
                }
 
        }
 
        next : 
        
if(!visit[t])break ; 
        
for(c=INT_MAX,j=t;j!=s;j=i) 
        

            i
=prev[j]; 
            
if(c>r[i][j])c=r[i][j]; 
        }
 
        
for(j=t;j!=s;j=i) 
        

            i
=prev[j]; 
            f[i][j]
+=c ; 
            f[j][i]
=-f[i][j]; 
            r[i][j]
=g[i][j]-f[i][j]; 
            r[j][i]
=g[j][i]-f[j][i]; 
        }
 
        flow
+=c ; 
    }
 
    
return flow ; 
}


void Floyd(int n,int map[][maxn])
{
    
int i,j,k;
    
for(k=0;k<n;k++){
        
for(i=0;i<n;i++){
            
for(j=0;j<n;j++){
                
if(map[i][k]+map[k][j]<map[i][j])
                    map[i][j]
=map[i][k]+map[k][j];
            }

        }

    }

}


int mat[maxn][maxn];
int tmp[maxn][maxn];
int mp[maxn][maxn];
int make[maxn][maxn];
int bus[maxn];

void build(int id)
{
    
int i,j;
    
for(i=0;i<id;i++){
        make[i][i
+id]=1;
        
for(j=0;j<id;j++){
            
if(mp[i][j])
                make[i
+id][j]=INF;
        }

    }

}


int main()
{
    
int n,m,p;
    
while(scanf("%d%d%d",&n,&m,&p)!=EOF)
    
{
        
if(n==0&&m==0&&p==0)break;
        
int i,j;
        
for(i=0;i<n;i++){
            
for(j=0;j<n;j++){
                mat[i][j]
=INF;
            }

            mat[i][i]
=0;
        }

        
for(i=0;i<m;i++){
            
int u,v;
            scanf(
"%d%d",&u,&v);
            
--u;--v;
            mat[u][v]
=1;
        }

    
        
for(i=0;i<n;i++){
            
for(j=0;j<n;j++){
            tmp[i][j]
=mat[i][j];
            }

        }
    
        Floyd(n,tmp);

        
if(p<tmp[0][n-1])
        
{
            printf(
"0\n");
            
continue;
        }

        
int id=0;
        
for(i=0;i<n;i++){
            
if(tmp[0][i]+tmp[i][n-1]<=p){
                bus[id
++]=i;
            }

        }

        
for(i=0;i<id;i++){
            
for(j=0;j<id;j++){
                mp[i][j]
=0;
                
if(mat[bus[i]][bus[j]]==1)
                    mp[i][j]
=1;
            }

        }

        build(id);
        printf(
"%d\n",Edmonds_Karp(2*id,make,id,id-1,f));
    }

    
return 0;
}

posted on 2009-11-21 21:08 Drolca 阅读(81) 评论(0)  编辑 收藏 引用


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